All challenges
Medium 0 solved 0% acceptance

Lexicographic Permutation

Find the k-th arrangement of some distinct characters in dictionary order.

What you'll learn

  • Skip whole blocks of permutations at once
  • Convert a rank to a permutation
  • Work with 0-based and 1-based positions

Problem

List every arrangement of the characters of s in dictionary order. For "abc" the list is abc, acb, bac, bca, cab, cba. Return the k-th entry, counting from 1. Generating the whole list is too slow for 12 characters (479,001,600 arrangements): each block of arrangements that starts with the same character has (length − 1)! entries, so you can pick one character at a time.

Implement lexicographic_permutation(s, k).

Input

s: Distinct characters in any order.

k: The position in the sorted list, counting from 1.

Output

Return the k-th arrangement as a string. Characters are compared by their character codes, so digits come before uppercase letters, which come before lowercase letters.

Constraints

1 ≤ s.length ≤ 12; all characters of s are distinct; 1 ≤ k ≤ s.length!

Examples

Example 1
Input:
s = "abc"
k = 4

Expected output:
expected = "bca"
Input:
std::string s = "abc";
long long k = 4;

Expected output:
std::string expected = "bca";
Input:
string s = "abc";
long k = 4;

Expected output:
string expected = "bca";

Explanation

The list is abc, acb, bac, bca, cab, cba, and the fourth is "bca".

Example 2
Input:
s = "312"
k = 1

Expected output:
expected = "123"
Input:
std::string s = "312";
long long k = 1;

Expected output:
std::string expected = "123";
Input:
string s = "312";
long k = 1;

Expected output:
string expected = "123";

Explanation

The first arrangement is the characters in sorted order: "123".

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Sort the characters first.

Hint 2

Each choice of first character covers (length − 1)! permutations, so dividing k − 1 by that number picks it.

Hint 3

Remove the chosen character, keep the remainder, and repeat with the rest.

Expected complexity

O(n²) time, O(n) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.