Finding Kth Permutation Sequence

Question

I have written a program to display the kth permutation sequence of a string made up of letters 'O' and 'Z' . I tried optimizing it but my code have not passed test cases due to timeout issues.Looking for someone who can guide me in optimizing the code i posted below.

public static void main(String[] args) throws IOException {

    /*
     * Sample Input 
     * 1 
     * 3 2 // Passing two inputs as single string
     * 
     * Sample Output
     * OOZ
     */

    // Scanner in = new Scanner(System.in);
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String line = br.readLine();
    // Getting 2 integer inputs with space
    String[] k1 = br.readLine().split("\\s");

    // String b1 = br.readLine();
    String eol = System.getProperty("line.separator");
    // byte[] eolb = eol.getBytes();

    long t = Integer.parseInt(line);

    long k = Integer.parseInt(k1[0]);
    long b = Integer.parseInt(k1[1]);
    char set1[] = { 'O', 'Z' };
    ArrayList<String> prefixlist = new ArrayList<String>();
    printAllKLength(set1, k, prefixlist, b);

}

static void printAllKLength(char set[], long k,
        ArrayList<String> prefixlist, long b) throws IOException {
    int n = set.length;
    BufferedOutputStream bout = new BufferedOutputStream(System.out);
    printAllKLengthRec(set, "", n, k, prefixlist);
    Collections.sort(prefixlist);
    if (b <= prefixlist.size()
            && prefixlist.contains(prefixlist.get((int) (b + 1)))) {

        byte b1[] = String.valueOf(prefixlist.get((int) (b - 1)))
                .getBytes();
        bout.write(b1);
        bout.write(System.lineSeparator().getBytes());
        bout.flush();
        // System.out.println(prefixlist.get((int) (b - 1)));
    } else {
        byte b1[] = "-1".getBytes();
        bout.write(b1);
        bout.write(System.lineSeparator().getBytes());
        bout.flush();
    }
}

static void printAllKLengthRec(char set[], String prefix, int n, long k,
        ArrayList<String> prefixlist) {

    if (k == 0) {

        if (!prefix.contains("ZZ")) {

            prefixlist.add(prefix);
        }

        return;
    }

    for (int i = 0; i < n; ++i) {

        String newPrefix = prefix + set[i];

        printAllKLengthRec(set, newPrefix, n, k - 1, prefixlist);
    }

}

Answer 1

You are hitting the time limit as you are supposed to only find the k-th permutation, but you are generating all permutations instead. Look at this discussion. You will probably have to replace the term (numberOfCharacters!) with (numberOfCharacters!/countO!/countZ!) as explained here.