Sign in Subscribe
By Vishal Basumatary in Hackerrank —

Hackerrank Bigger is Greater Solution

Hackerrank Bigger is Greater Solution

.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

Lexicographical order is often known as alphabetical order when dealing with strings.  A string is greater than another string if it comes later in a lexicographically sorted list.

Given a word, create a new word by swapping some or all of its characters.  This new word must meet two criteria:

  • It must be greater than the original word
  • It must be the smallest word that meets the first condition

For example, given the word , the next largest word is .

Complete the function biggerIsGreater below to create and return the new string meeting the criteria.  If it is not possible, return no answer.

Function Description

Complete the biggerIsGreater function in the editor below.  It should return the smallest lexicographically higher string possible from the given string or no answer.

biggerIsGreater has the following parameter(s):

  • w: a string

Input Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

The first line of input contains , the number of test cases.
Each of the next  lines contains .

Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

  • will contain only letters in the range ascii[a..z].

Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

For each test case, output the string meeting the criteria.  If no answer exists, print no answer.

Sample Input 0.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} 5abbbhefgdhckdkhc

Sample Output 0.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} bano answerhegfdhkchcdk

Explanation 0.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

  • Test case 1:
    ba is the only string which can be made by rearranging ab. It is greater.
  • Test case 2:
    It is not possible to rearrange bb and get a greater string.
  • Test case 3:
    hegf is the next string greater than hefg.
  • Test case 4:
    dhkc is the next string greater than dhck.
  • Test case 5:
    hcdk is the next string greater than dkhc.

Sample Input 1.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} 6lmnodcbadcbbabdcabcdfedcbabcd

Sample Output 1.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} lmonno answerno answeracbdabdcfedcbabdc

Solution in java8

Approach 1.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int ti = 1; ti <= t; ti++) {
            char[] chs = sc.next().toCharArray();
            int len = chs.length;
            
            int lastSeen = chs[len-1];
            int i = len - 2;
            while (i >= 0 && chs[i] >= lastSeen) {
                lastSeen = chs[i];
                i--;
            }
            if (i < 0) {
                System.out.println("no answer");
                continue;
            }
            
            Arrays.sort(chs, i+1, len);
            
            int j = i+1;
            while ( j < len && chs[j] <= chs[i]) j++;
            
            char temp = chs[i];
            chs[i] = chs[j];
            chs[j] = temp;

            System.out.println(new String(chs));
        }
    }
}

Approach 2.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        in.nextLine();
        while (T-- > 0) {
            String s = in.nextLine();
            int l = s.length();
            char c[] = s.toCharArray();
            boolean fix = false;
            int startind = -1;
            for (int i = l - 1; i >= 0; i--) {
                int index = -1;
                char min = (char)255;
                for (int j = i + 1; j < l; j++)
                    if (c[j] > c[i] && c[j] < min) {index = j; min = c[j];}
                if (index != -1) {char tmp = c[i]; c[i] = c[index]; c[index] = tmp; fix = true; startind = i + 1; break;}
            }
            if (!fix) {System.out.println("no answer"); continue;}
            Arrays.sort(c, startind, l);
            String ans = new String(c);
            System.out.println(c);
        }
    }
}

Approach 3.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.nextLine());

        String [] inputs = new String[n];
        for(int i=0;i<n;i++) 
        {
          inputs[i] = scan.nextLine();
        }
        for(int j=0;j<n;j++) 
        {
            char[] a = inputs[j].toCharArray();
            int pivot=-1;
            int k=-1;
            for(int i=a.length-1; i>0;i--) {
                if(a[i] > a[i-1]) {
                    pivot = i-1;
                    break;
                }
            }
            if(pivot ==-1)
            { System.out.println("no answer");
              continue;
            }
            for(int i=a.length-1;i>pivot;i--) 
            {
                if(a[i] > a[pivot]) 
                {
                   k= i;
                   break;
                }
            }            
            char tmp = a[k];
            a[k] = a[pivot];
            a[pivot] = tmp;
            for(int i=1;i<=(a.length-1-pivot)/2;i++) {
                tmp = a[pivot+i];
                a[pivot+i] =  a[a.length-i];
                a[a.length-i] = tmp;
            }
            System.out.println(String.valueOf(a));
        }
    
    }
}

Solution in python3

Approach 1.

import sys 
from itertools import permutations

def nextperm(w):
    for x in range(len(w)-1,0,-1):
        if w[x-1]<w[x]:
               for y in range(len(w)-1,x-1,-1):
                    if w[y] > w[x-1]:
                        return w[:x-1] + w[y:y+1] + w[:y:-1] + w[x-1:x] + w[y-1:x-1:-1]
    return "no answer"
 


t = int(input())

for x in range(t):
    w = input()
    result = nextperm(w)
    print(result)

Approach 2.

for _ in range(int(input())):
    s = input()
    has_greater = False
    for i in range(len(s)-1)[::-1]:
        if ord(s[i]) < ord(s[i+1]):
            for j in range(i+1,len(s))[::-1]:
                if ord(s[i]) < ord(s[j]):
                    lis = list(s)
                    lis[i],lis[j]=lis[j],lis[i]
                    print("".join(lis[:i+1]+lis[i+1:][::-1]))
                    has_greater = True
                if has_greater == True:
                    break
        if has_greater == True:
            break
    if has_greater == False:
        print("no answer")

Approach 3.

for i in range(int(input())):
    s = input()
    has_greater = False
    for i in range(len(s)-1)[::-1]:
        if ord(s[i]) < ord(s[i+1]):
            for j in range(i+1,len(s))[::-1]:
                if ord(s[i]) < ord(s[j]):
                    lis = list(s)
                    lis[i],lis[j]=lis[j],lis[i]
                    print("".join(lis[:i+1]+lis[i+1:][::-1]))
                    has_greater = True
                if has_greater == True:
                    break
        if has_greater == True:
            break
    if has_greater == False:
        print("no answer")

Solution in cpp

Approach 1.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {

   int t;cin>>t;
    while(t)
     {  string str;
        cin>>str;
        int f= next_permutation(str.begin(),str.end());
      if(f==0)
      { cout<<"no answer"<<endl;}
      else
      {cout<<str<<endl;}
        t--;
    }
    return 0;
}

Approach 2.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() 
{
    bool flag = 0;
    string str;
    long T;
    cin>>T;
    while(T--)
    {
       cin>>str;
	   if(next_permutation(str.begin(),str.end()))
           cout<<str<<endl;
        else
            cout<<"no answer"<<endl;
	}
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    return 0;
}

Approach 3.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;



void GetSmallestBigger(const string& input, string& output)
{
	output = input;

	if (!next_permutation(output.begin(), output.end()))
	{
		output = "no answer";
	}
}


int main()
{

	int N = 0;

	cin >> N;

	for (size_t i = 0; i < N; i++)
	{
		//string input = "zyyxwwtrrnmlggfeb";
		string input;
		string output;
		cin >> input;
		GetSmallestBigger(input, output);
		if (i == N - 1)
			cout << output;
		else
			cout << output << endl;
	}

	return 0;
}

Subscribe to The Poor Coder | Algorithm Solutions

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
[email protected]
Subscribe