715457. Find Kth permutation
Find Kth Permutation
Slug: find-kth-permutation-0932
Difficulty: Medium
Id: 715457
Topic Tags: Backtracking, Algorithms
Company Tags: None
Summary
Given a string S and an integer K, write a function to generate the Kth permutation of the characters in S. The permutations are generated in lexicographic sort order.
Detailed Explanation
To solve this problem, we can use backtracking algorithm. The idea is to generate all permutations of the string and return the Kth one. We start by selecting the smallest character that has not been used yet and place it at the beginning of the permutation. Then, we recursively generate all remaining permutations for the remaining characters.
Here's a step-by-step breakdown of the solution:
- Initialize an empty string
permto store the Kth permutation. - Sort the input string S in ascending order.
- For each character
cin S:- If
kis greater than 0, appendctopermand decrementk. - Recursively generate all permutations for the remaining characters (i.e., S without
c) untilkbecomes 0.
- If
- Return
perm.
The time complexity of this algorithm is O(n!), where n is the length of the input string, because we need to generate all permutations. The space complexity is O(n), because we need to store the permutation.
Optimized Solutions
Java
public String findKthPermutation(String s, int k) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
StringBuilder perm = new StringBuilder();
backtrack(chars, k, perm);
return perm.toString();
}
private void backtrack(char[] chars, int k, StringBuilder perm) {
if (k == 1) {
for (char c : chars) {
perm.append(c);
}
} else {
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
chars = Arrays.copyOfRange(chars, i + 1, chars.length);
backtrack(chars, k - 1, perm);
perm.append(c);
}
}
}