HackerRank Bigger is Greater Problem Solution

In this post, we will solve HackerRank Bigger is Greater Problem Solution.

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

Example
w = abcd
The next largest word is abdc.
Complete the function biggerlsGreater below to create and return the new string meeting
the criteria. If it is not possible, return no answer.

Function Description
Complete the biggerlsGreater function in the editor below.
biggerlsGreater has the following parameter(s):

string w: a word
Return
string: the smallest lexicographically higher string possible or no answer

Input Format
The first line of input contains T, the number of test cases.
Each of the next T lines contains w.

Sample Input 0

5
ab
bb
hefg
dhck
dkhc

Sample Output 0

ba
no answer
hegf
dhkc
hcdk

Explanation 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

6
lmno
dcba
dcbb
abdc
abcd
fedcbabcd

Sample Output 1

lmon
no answer
no answer
acbd
abdc
fedcbabdc

Table of Contents

Bigger is Greater C Solution

#include <stdio.h>
#include <string.h>
void Merge(int *arr,int left,int mid,int right)
{
  int newArray[right-left+1];
  int pos=0,lpos=left,rpos=mid+1;
  while(lpos<=mid && rpos<=right)
  {
    if(arr[lpos]<arr[rpos])
    {
      newArray[pos++]=arr[lpos++];
    }
    else
    {
      newArray[pos++]=arr[rpos++];
    }
  }
  while(lpos<=mid)
  {
    newArray[pos++]=arr[lpos++];
  }
  while(rpos<=right)
  {
    newArray[pos++]=arr[rpos++];
  }
  int i;
  for(i=0;i<pos;i++)
  {
    arr[i+left]=newArray[i];
  }
  return;
}

void MergeSort(int *arr,int left,int right)
{
  int mid;
  mid=(left+right)/2;
  if(left<right)
  {
    MergeSort(arr,left,mid);
    MergeSort(arr,mid+1,right);
    Merge(arr,left,mid,right);
  }
  return;
}

int main()
{
	int t,i,j,note,index,no;
	char w[100];
	scanf("%d",&t);
	while(t--)
	{
		char temp;
		int temp_c,flag=0;
		int count=0,len_w=0;
		scanf("%s",w);
		len_w=strlen(w);
		note=0;
		for(i=len_w-1;i>0;i--)
		{
			temp=i;
			if(w[--temp]<w[i])
			{				
				temp_c=w[temp]-97;
				note=temp;
				break;
			}
			flag++;
		}
		
		int arr[len_w-note];
		for(i=0;i<len_w-note;i++)
		{			
			arr[i]=w[temp]-97;
			temp++;
		}
		//printf("sade\n");
		MergeSort(arr,0,len_w-note-1);
		
			
		for(i=0;i<len_w-note;i++)
		{
			if(arr[i]>temp_c)
			{
				 index=i;
				 no=arr[i];
				 break;
			}
		}
		if(flag==len_w-1)
			printf("no answer\n");
		else
		{
		for(i=0;i<note;i++)
		{
			printf("%c",w[i] );
		}
		printf("%c",no+97 );
		for(i=0;i<len_w-note;i++)
		{
			if(i!=index)
				printf("%c",arr[i]+97 );
		}
		printf("\n");
		}
	}//madarchod
	return 0;
}

Bigger is Greater C++ Solution

#include <bits/stdc++.h>
#define MAX_N 150 
#define oo 200 

using namespace std;

int test; 
int n; 
string s; 
char a[MAX_N]; 

int main ()
{
	ios :: sync_with_stdio(false);
	cin.tie(0); 
	
	cin >> test; 
	
	while (test--)
	{
		cin >> s; 
		
		n = s.size(); int flag = 0; int pos; 
		
		for (int i = 1; i <= n; i++) a[i] = s[i - 1]; 
		
		for (int i = n - 1; i >= 1; i--) 
		{
			int mini = oo; int p;  
			
			for (int j = i + 1; j <= n; j++) 
				if (a[i] < a[j]) 
				{
					flag = 1; 
					if (mini > a[j]) 
					{
						mini = a[j]; 
						p = j; 
					}
				}
				
			if (flag) 
			{
				//cout << p << endl; 
				pos = i; 
				swap(a[i] , a[p]); 
				break; 
			}
		}
		
		if (!flag) cout << "no answer"; 
		else 
		{
			//cout << pos << endl; 
			sort(a + pos + 1, a + n + 1); 
			
			for (int i = 1; i <= n; i++) cout << a[i]; 
		}
		
		cout << endl; 
	}
	return 0;
}

Bigger is Greater C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
class Solution {
    static void Main(String[] args) {
        int charSpace = (int)'z'-(int)'a'+1;        
        int cases = int.Parse(Console.ReadLine());
        
        for(int j =0; j< cases; j++)
        {
            int[] charsToRearrange = new int[charSpace];
            string word = Console.ReadLine();
            
            char last = word[word.Length-1];
            int turningPoint = -1;
            for(int i = word.Length-2; i>=0; i--)
                {
                int lastIndex = getIndex(last);
                charsToRearrange[lastIndex]++;
                if((int)last > (int)word[i])
                {
                    turningPoint = i;
                    break;
                }   
                last = word[i];
            }
            if(turningPoint == -1)
                {
                Console.WriteLine("no answer");
                continue;
            }
            StringBuilder output = new StringBuilder();
            
            output.Append(word.Substring(0,turningPoint));
            
            int indexAfterTurningPoint = getIndex(word[turningPoint]) + 1;
            
            for(int i = indexAfterTurningPoint; i< charSpace ; i++)
                {
                if(charsToRearrange[i]>0)
                    {
                        charsToRearrange[getIndex(word[turningPoint])]++;
                        output.Append(getChar(i));
                        charsToRearrange[i]--;
                        break;
                    }
            }
            
            for(int i = 0 ; i< charSpace; i++)
                {
                while(charsToRearrange[i]>0)
                    {
                        output.Append(getChar(i));
                        charsToRearrange[i]--;                        
                    }
            }
            Console.WriteLine(output.ToString());
        }
    }
    
    static char getChar(int index)
    {
        return (char) (index + (int)'a');
    }
    
    static int getIndex(char character)
    {
        return (int)character - (int)'a';
    }
}

Bigger is Greater Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'biggerIsGreater' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts STRING w as parameter.
     */

    public static String biggerIsGreater(String w) {
    // Write your code here
 if (w.length() <= 1) {
            return "no answer";
        }
        StringBuilder stringBuilder = new StringBuilder(w);
        boolean done = false;
        int indexToSwap = stringBuilder.length()-1;
        for (int i = stringBuilder.length()-1; i > 0 ; i--) {
            int a = stringBuilder.charAt(i-1);
            int b = stringBuilder.charAt(i);
            if (b > a) {
                indexToSwap = i - 1;
                done = true;
                break;
            }
        }
        if (!done) {
            return "no answer";
        }
        int charToSwap = stringBuilder.charAt(indexToSwap);
        int charLeastExceeding = stringBuilder.charAt(indexToSwap + 1);
        int indexLeastButExceeding = indexToSwap + 1;
        for (int i = indexToSwap + 1; i < stringBuilder.length(); i++) {
            int currentChar = stringBuilder.charAt(i);
            if (currentChar > charToSwap && currentChar < charLeastExceeding) {
                charLeastExceeding = currentChar;
                indexLeastButExceeding = i;
            }
        }
        stringBuilder.setCharAt(indexToSwap, (char)charLeastExceeding);
        stringBuilder.setCharAt(indexLeastButExceeding, (char)charToSwap);
        List<Character> chars = new ArrayList<>();
        for (int i = indexToSwap + 1; i < stringBuilder.length(); i++) {
            chars.add(stringBuilder.charAt(i));
        }
        Collections.sort(chars);
        for (int i = 0; i < chars.size(); i++) {
            stringBuilder.setCharAt(indexToSwap + 1 + i, chars.get(i));
        }
        return stringBuilder.toString();
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int T = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, T).forEach(TItr -> {
            try {
                String w = bufferedReader.readLine();

                String result = Result.biggerIsGreater(w);

                bufferedWriter.write(result);
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Bigger is Greater JavaScript Solution

function processData(input) {
    var tests = input.split('\n');
    tests.shift();
    tests.forEach(function (str) {
        var lex = getLexBigger (str);
        if (!lex)
            console.log('no answer');
        else
            console.log(lex);  
    });
} 
/*
    Find largest index i such that array[i − 1] < array[i].
    Find largest index j such that j ≥ i and array[j] > array[i − 1].
    Swap array[j] and array[i − 1].
    Reverse the suffix starting at array[i].
*/
function getLexBigger (str) {
    var strArr = str.split('');
    var i = strArr.length-1;
    // aaaaaaaabbbccddeeeed i=19
    //console.log('i1:'+i)
    // [a,b] i=1
    // [k,u,e,m,g,b] i=5
    while (i > 0 && strArr[i-1] >= strArr[i]) {
        i--;
    }
    //console.log('i2:'+i)
    // aaaaaaaabbbccddeeeed i=15
    // [a,b] i=1
    // [k,u,e,m,g,b] i=3
    
    if (i === 0)
        return null;
    
    var j = strArr.length-1;
    //console.log('j1:'+j)
    // [a,b] i=1 j=1
    // [k,u,e,m,g,b] i=3 j=5
    while (j > i && strArr[j] <= strArr[i-1]) {
        j--;
    }
    //console.log('j2:'+j)
    // [k,u,e,m,g,b] i=3 j=4 i-1=e

    if (j >= i) {
        //console.log('swap:'+strArr[i-1] + ' > ' + strArr[j])
        var temp = strArr[i-1];
        strArr[i-1] = strArr[j];
        strArr[j] = temp;
    }
    //           [k,u,g,m,e,b] i=3 j=4 i-1=e
    // should be [k,u,m,e,g,b]
    // next reverse end of array
    var tempArr = strArr.splice(i, strArr.length);
    tempArr.reverse();
    strArr = strArr.concat(tempArr)
    //           [k,u,g,b,e,m] i=3 j=4 i-1=e
    // should be [k,u,m,e,g,b]
    
    return strArr.join('');
   
 }  

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Bigger is Greater Python Solution

def bigger(string):
    arr = list(string)
    index = None
    for i in range(0, len(arr)-1)[::-1]:
        if arr[i] < arr[i+1]:
            index = i
            break
    if index is None:
        return 'no answer'
    for i in range(index, len(arr))[::-1]:
        if arr[i] > arr[index]:
            arr[index], arr[i] = arr[i], arr[index]
            break
    lo, hi = index+1, len(arr)-1
    while lo < hi:
        arr[lo], arr[hi] = arr[hi], arr[lo]
        lo, hi = lo+1, hi-1
    res = ''.join(arr)
    return res

if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        s = input().rstrip()
        print(bigger(s))