Interview Questions

Sort lexicographically - Bigger is greater

Problem Statement:

Given a word , rearrange the letters of to construct another word in such a way that is lexicographically greater than . In case of multiple possible answers, find the lexicographically smallest one among them.

Input Format

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

Constraints


will contain only lower-case English letters and its length will not exceed .

Output Format

For each testcase, output a string lexicographically bigger than in a separate line. In case of multiple possible answers, print the lexicographically smallest one, and if no answer exists, print no answer.

Sample Input

5
ab
bb
hefg
dhck
dkhc

Sample Output

ba
no answer
hegf
dhkc
hcdk

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.util.Scanner;


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 sc = new Scanner(System.in);
        int n = sc.nextInt();
       
        for(int i=0;i<n;i++)
            {
           
            String s = sc.next();
            sortNext(s);
        }
    }
   
    public static void sortNext(String s)
        {
        char[] strArr = new char[s.length()];
        for(int i=0;i<s.length();i++)
            {
            strArr[i]=s.charAt(i);
        }
       
         if(s.length()==1)
        {
                System.out.println("no answer");
                return;
        }
      //  System.out.println(Arrays.toString(strArr));
        boolean swap = false;
        for(int i=0;i<strArr.length;i++)
            {
           
                if(i+1<strArr.length && strArr[i+1]>strArr[i])
                {
                        continue;
                }
                else if(i+1<strArr.length && strArr[i+1]<=strArr[i])
                {
                        int g = strArr.length-2;
                        while(!swap && g>=0){
                        swap = swap(strArr,g);
                       
                        g--;
                        }
                        if(swap == false)
                        {
                                System.out.println("no answer");
                                return;
                        }
                       
       
                }
                if(swap==false)
                {
                        int temp = strArr[strArr.length-1];
                        strArr[strArr.length-1] = strArr[strArr.length-2];
                        strArr[strArr.length-2]=(char)temp;
                       
                        String finalStr = new String(strArr);
                    if(!s.equals(finalStr))
                        System.out.println(finalStr);
                    else
                        System.out.println("no answer");
                        return;
                }
                else{
               
                System.out.println(new String(strArr));
                return;
                }
        }
       
       
    }
   
    public static boolean swap(char[] arr,int i)
    {
        //System.out.println(arr[i]);
        int max = 0;
        int val = arr[i];
        int maxPos = -1;
        for(int j=i+1;j<arr.length;j++)
        {
                if(arr[j]>val){
                        if(arr[j]<max)
                       
                                {max=arr[j];maxPos = j;}
                        else if(max==0)
                        {
                                max = arr[j];
                                maxPos = j;
                        }
                }
        }
       
        if(max>0)
        {
                //System.out.println("max-"+(char)max);
                arr[i]=(char)max;
                arr[maxPos]=(char)val;
                //System.out.println(Arrays.toString(arr));
        }
        else{
                return false;
        }
        int temp = 0;
        int n  = arr.length;
         for(int k=i+1;k  < n; k++){
             for(int l=i+2; l < n; l++){
                   
                     if(arr[l-1] > arr[l]){
                             //swap the elements!
                             temp = arr[l-1];
                             arr[l-1] = arr[l];
                             arr[l] = (char)temp;
                     }
                   
             }
     }
         
        // System.out.println(Arrays.toString(arr));
         return true;
    }
}