0
\$\begingroup\$

I have tried many possible methods here but I am still not able to reduce the time complexity of below algorithm.

//This function returns the next lexicographical permutation of the StringBuilder s
static 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;

}⁠⁠⁠⁠

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 3
4 5 4

which 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.

\$\endgroup\$
  • \$\begingroup\$ For an algorithm that has a complexity linear to the length of the string, see the last part of this answer: stackoverflow.com/questions/34230266/… \$\endgroup\$ – m69 May 10 '17 at 4:46
1
\$\begingroup\$

Let P(n,m) be the number of permutations of n Hs and m Vs. For m>0 and n>0, P(n,m) = (n + m)!/(n! * m!).

Let's say you want the kth permutation of n Hs and m Vs:

If k <= P(n-1,m), then the answer is an H followed by the kth permutation of n-1 Hs and m Vs.

Otherwise the answer is a V followed by the (k-P(n-1,m))th permutation of n Hs and m-1 Vs.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for the suggestion Matt. I have yet to try out this approach. But I am guessing this will flow towards memoization technique using DP. Correct me if I am wrong. \$\endgroup\$ – CodeHunter May 10 '17 at 3:49
  • 1
    \$\begingroup\$ You can implement it recursively or iteratively pretty much the way I said it. There aren't any overlapping subproblems since since solving the problem only requires solving one smaller subproblem, and DP is not required. \$\endgroup\$ – Matt Timmermans May 10 '17 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.