I have tried many possible methods here but I am still not able to reduce the time complexity of below algorithm. The basic layout of my problem is as follows:I have a string that is composed of only H's and V's. There can be not more than 10 H's and 10 V's possible. I need to find the Kth lexicographical order of such pattern. Also, inp[] array contains input is format:2 2 34 5 4which means that total H = 2, total V = 2 and I need to print 3rd lexicographical permutation of HHVV.Similarly for 4 5 4, I need to print 4th lexicographical permutation of HHHHVVVVV.//This function returns the next lexicographical permutation of the StringBuilder sstatic StringBuilder getKRankString(StringBuilder s){    char ch[] = (s.toString()).toCharArray();          int i = 0, j=0;    //This loop gets the highest i for which ch[i]<ch[i+1]    for(int k=0;k<s.length()-2;k++){        if(ch[s.length()-2-k]<ch[s.length()-1-k]){            i = s.length()-2-k;            break;        }    }    //System.out.println(i);    //This loop gets the highest j for which ch[j]>ch[i]    for(int k=s.length()-1;k>i;k--){        if(ch[k]>ch[i]){            j = k;            break;        }    }    //System.out.println(j);    //swap characters at i and j    char temp = ch[i];    ch[i] = ch[j];    ch[j] = temp;    //Append the original string till i to reversed string from i till end    StringBuilder swapped = new StringBuilder(new String(ch));    //System.out.println(swapped);    String sb1 = swapped.substring(0, i+1);    String sb2 = (new StringBuilder(swapped.substring(i+1, s.length())).reverse()).toString();    StringBuilder str = new StringBuilder(sb1+sb2);    return str;   }    static String[] gridLand(String[] inp) {    String[] outputArr = new String[inp.length];    for(int i=0;i<inp.length;i++){    //get the first line of input and get integer x and y        int x = Integer.valueOf(inp[i].split( )[0]);        int y = Integer.valueOf(inp[i].split( )[1]);        int k = Integer.valueOf(inp[i].split( )[2]);        StringBuilder sb = new StringBuilder();    //form the original string using x H's and y V's.    //This will be the first String of this order        for(int j = 0; j < x; j++)            sb = sb.append(H);        for(int j = 0; j < y; j++)            sb = sb.append(V);        //String s1 = sb.toString();    //run the below functoin K times to get Kth lexicographical string        for(int m = 0; m < k; m++)            sb = getKRankString(sb);        outputArr[i] = sb.toString();    }    return outputArr;}
Find lexicographical permutations
java;performance;algorithm;complexity
EncodingI hope I understood the problem correctly :)When observing the problem, I found you can replace the H and V with 0 and 1. The lexicographical permutations then become binary numbers. There are only 10 V's and 10 H's, so the final number will be below 2^20 so fits even in an int.   HHHVV -> 00011   VVHHH -> 11000   etc.Start out by setting the starting int to  (1 << Vs) -1 and use the next-bit permutation logic from hereThen, if you found the nth permutation, transform it back to a StringTime complexityAs calculation the next bit permutation is simply a constant time calculation, finding the nth permutation takes O(n) time.Proposed solutionpublic class Permutations{    //treat H as 0, V as 1.    private static String getLongAsHVString( long size, long l )    {        String s = Long.toBinaryString( l ).chars().mapToObj( Permutations::getStr ).collect( Collectors.joining() );        //Prepend the 'missing' zeroes as 'H' s        while ( s.length() < size )        {            s = H + s;        }        return s;    }    private static String getStr( int c )    {        return ( c == '0' ) ? H : V;    }    private static long getNthLexoPerm( int hCount, int vCount, int n )    {        long current = ( 1 << vCount ) - 1;        for ( int i = 0; i < n; i++ )        {            current = nextPerm( current );        }        return current;    }    private static String getNthLexoPermAsString( int hCount, int vCount, int n )    {        return getLongAsHVString( hCount + vCount, getNthLexoPerm( hCount, vCount, n ) );    }    public static long nextPerm( long v )    {        long t = ( v | ( v - 1 ) ) + 1;        return t | ( ( ( ( t & -t ) / ( v & -v ) ) >> 1 ) - 1 );    }    public static void main( String[] args )    {        System.out.println( getNthLexoPermAsString( 2, 2, 3 ) );        System.out.println( getNthLexoPermAsString( 4, 5, 4 ) );    }}