Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Lexicographic Permutation

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

Bạn sẽ học được gì

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

Đề bài

Xem bản dịch

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.

Ràng buộc

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

Ví dụ

Ví dụ 1
Đầu vào:
s = "abc"
k = 4

Kết quả mong đợi:
expected = "bca"
Đầu vào:
std::string s = "abc";
long long k = 4;

Kết quả mong đợi:
std::string expected = "bca";
Đầu vào:
string s = "abc";
long k = 4;

Kết quả mong đợi:
string expected = "bca";

Giải thích

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

Ví dụ 2
Đầu vào:
s = "312"
k = 1

Kết quả mong đợi:
expected = "123"
Đầu vào:
std::string s = "312";
long long k = 1;

Kết quả mong đợi:
std::string expected = "123";
Đầu vào:
string s = "312";
long k = 1;

Kết quả mong đợi:
string expected = "123";

Giải thích

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

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Sort the characters first.

Gợi ý 2

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

Gợi ý 3

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

Độ phức tạp mong đợi

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

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.