K-th Lexicographic Permutation of a String

Problem

Given a string s of length n (assume characters are distinct) and an integer k (1-indexed), return the k-th permutation of s in lexicographic order.

If the input contains duplicate characters, the factoradic method treats equal characters as distinct positions — to get the k-th unique permutation with duplicates use a frequency-aware method (see related notes).

Examples

Example 1

Input: s = "abc", k = 4
Output: "bca"

Example 2

Input: s = "1234", k = 14
Output: "cbad"

Solution

Method 1 — Brute force

Intuition

Generate all permutations of the input string (we already discussed generation methods in [All permutations of a string 1 - String has no duplicates](all-permutations-of-a-string-with-distinct-characters) and [All permutations of a string 2 - String has duplicates](all-permutations-of-a-string-with-duplicate-characters)). Sort the generated list and return the k-th element. A variant of brute force generates permutations in lexicographic order directly (prefix/suffix recursion), but that still requires enumerating up to k permutations and is therefore inefficient in the worst case.

Approach

• Generate all permutations (or generate until you reach the k-th if you use an ordered generator).

• Sort the list of permutations.

• Return the k-th element (1-indexed).

• Drawbacks: factorial time and space in n — not practical for moderate n.

Method 2 — Factoradic (direct construction)

Intuition

Write k-1 in the factorial number system (factoradic). Each digit tells which element to pick from the remaining sorted list of characters for the next position.

Approach

• Precompute factorials fact[0..n].
• Convert k to 0-index by k -= 1.
• Maintain a list nums of sorted characters.
• For i = n down to 1:
  • idx = k / fact[i-1]
  • k = k % fact[i-1]
  • append and remove nums[idx].
• Return the constructed string.

This is O(n^2) using a dynamic array for removals.

Code

C++

class Solution {
public:
  string kthPermutation(string s, long long k) {
    int n = s.size();
    vector<long long> fact(n+1, 1);
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1] * i;
    --k; // 0-index
    string ans;
    vector<char> nums(s.begin(), s.end());
    sort(nums.begin(), nums.end());
    for (int i = n; i >= 1; --i) {
      long long f = fact[i-1];
      int idx = (int)(k / f);
      k %= f;
      ans.push_back(nums[idx]);
      nums.erase(nums.begin() + idx);
    }
    return ans;
  }
};

Go

package main

import "sort"

func kthPermutation(s string, k int) string {
    n := len(s)
    fact := make([]int, n+1)
    fact[0] = 1
    for i := 1; i <= n; i++ { fact[i] = fact[i-1] * i }
    k-- // 0-index
    nums := []rune(s)
    sort.Slice(nums, func(i, j int) bool { return nums[i] < nums[j] })
    res := make([]rune, 0, n)
    for i := n; i >= 1; i-- {
        f := fact[i-1]
        idx := k / f
        k = k % f
        res = append(res, nums[idx])
        nums = append(nums[:idx], nums[idx+1:]...)
    }
    return string(res)
}

Java

import java.util.*;

class Solution {
  public String kthPermutation(String s, long k) {
    int n = s.length();
    long[] fact = new long[n+1];
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1] * i;
    k = k - 1; // 0-index
    List<Character> nums = new ArrayList<>();
    for (char c : s.toCharArray()) nums.add(c);
    Collections.sort(nums);
    StringBuilder ans = new StringBuilder();
    for (int i = n; i >= 1; --i) {
      long f = fact[i-1];
      int idx = (int)(k / f);
      k = k % f;
      ans.append(nums.remove(idx));
    }
    return ans.toString();
  }
}

Kotlin

class Solution {
  fun kthPermutation(s: String, kIn: Long): String {
    val n = s.length
    val fact = LongArray(n+1)
    fact[0] = 1
    for (i in 1..n) fact[i] = fact[i-1] * i
    var k = kIn - 1L
    val nums = s.toCharArray().sorted().toMutableList()
    val sb = StringBuilder()
    for (i in n downTo 1) {
      val f = fact[i-1]
      val idx = (k / f).toInt()
      k %= f
      sb.append(nums.removeAt(idx))
    }
    return sb.toString()
  }
}

Python

class Solution:
    def kth_permutation(self, s: str, k: int) -> str:
        n = len(s)
        fact = [1] * (n + 1)
        for i in range(1, n + 1):
            fact[i] = fact[i-1] * i
        k -= 1  # convert to 0-index
        nums = sorted(list(s))
        ans: list[str] = []
        for i in range(n, 0, -1):
            f = fact[i-1]
            idx = k // f
            k %= f
            ans.append(nums.pop(idx))
        return ''.join(ans)

Rust

pub struct Solution;
impl Solution {
    pub fn kth_permutation(s: String, mut k: usize) -> String {
        let mut nums: Vec<char> = s.chars().collect();
        nums.sort();
        let n = nums.len();
        let mut fact = vec![1usize; n+1];
        for i in 1..=n { fact[i] = fact[i-1] * i; }
        k -= 1; // 0-index
        let mut ans = String::with_capacity(n);
        for i in (1..=n).rev() {
            let f = fact[i-1];
            let idx = k / f;
            k %= f;
            ans.push(nums.remove(idx));
        }
        ans
    }
}

TypeScript

export class Solution {
  kthPermutation(s: string, k: number): string {
    const n = s.length;
    const fact = new Array<number>(n+1).fill(1);
    for (let i = 1; i <= n; ++i) fact[i] = fact[i-1] * i;
    k -= 1; // 0-index
    const nums = s.split('').sort();
    const res: string[] = [];
    for (let i = n; i >= 1; --i) {
      const f = fact[i-1];
      const idx = Math.floor(k / f);
      k = k % f;
      res.push(nums.splice(idx, 1)[0]);
    }
    return res.join('');
  }
}

Complexity

• ⏰ Time complexity: O(n^2) using dynamic array removals; O(n log n) or O(n) improvements are possible with advanced data structures.
• 🧺 Space complexity: O(n) auxiliary plus output.

Method 3 — Repeat next_permutation k-1 times

Intuition

Starting from the smallest permutation (sorted input), calling next_permutation repeatedly advances lexicographic order by one. Doing this k-1 times yields the k-th permutation.

Approach

• Sort s.
• Loop k-1 times calling next_permutation (or implement it yourself), stopping early if no next permutation exists.

Code

C++

class Solution2 {
public:
  string kthPermutationByNext(string s, long long k) {
    sort(s.begin(), s.end());
    for (long long i = 1; i < k; ++i) {
      if (!next_permutation(s.begin(), s.end())) break;
    }
    return s;
  }
};

Python

class Solution2:
    def kth_permutation_by_next(self, s: str, k: int) -> str:
        arr = sorted(list(s))
        if k <= 1: return ''.join(arr)
        def next_perm(a: list[str]) -> bool:
            i = len(a) - 2
            while i >= 0 and a[i] >= a[i+1]:
                i -= 1
            if i < 0: return False
            j = len(a) - 1
            while a[j] <= a[i]:
                j -= 1
            a[i], a[j] = a[j], a[i]
            a[i+1:] = reversed(a[i+1:])
            return True
        for _ in range(1, k):
            if not next_perm(arr): break
        return ''.join(arr)

Complexity

• ⏰ Time complexity: O(k * n).
• 🧺 Space complexity: O(n).