Samkit5025

Finding the Kth smallest string

May 17th, 2022
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.33 KB | None | 0 0
  1.  
  2. import java.util.Vector;
  3. import java.util.*;
  4.  
  5. public class Test {
  6.    
  7.     static Scanner sc = new Scanner(System.in);
  8.    
  9.     public static void swap(char ch[],int i,int j) {
  10.         char temp = ch[i];
  11.         ch[i] = ch[j];
  12.         ch[j] = temp;
  13.     }
  14.    
  15.     public static void findingAllRearrangements(char ch[],int n,Vector<String> v,int itr){
  16.         if(itr==n-1){
  17.             String s = "";
  18.             for(char i : ch) {
  19.                 s+=i;
  20.             }
  21.             v.add(s);
  22.             return;
  23.         }
  24.         HashSet<Character> hs = new HashSet<Character>();
  25.         for(int i=itr;i<n;i++) {
  26.             if(!hs.contains(ch[i])) {
  27.                 hs.add(ch[i]);
  28.                 swap(ch,itr,i);
  29.                 findingAllRearrangements(ch,n,v,itr+1);
  30.                 swap(ch,itr,i);
  31.             }
  32.         }
  33.     }
  34.  
  35.     public static String findingKthSmallest(int n, int k, String s){
  36.         char ch[] = s.toCharArray();
  37.         Vector<String> v = new Vector<String>();
  38.         findingAllRearrangements(ch,n,v,0);
  39.         Collections.sort(v);
  40.         if(k<=v.size()) {
  41.             return v.get(k-1);
  42.         }
  43.         return "-1";
  44.     }
  45.    
  46.     public static void main(String[] args) {
  47.         int n = sc.nextInt();
  48.         int k = sc.nextInt();
  49.         String s = sc.next();
  50.        
  51.         System.out.println(findingKthSmallest(n,k,s));
  52.     }
  53.  
  54. }
Advertisement
Add Comment
Please, Sign In to add comment