README_EN.md

comments	difficulty	edit_url	tags
true	Hard	https://github.com/doocs/leetcode/edit/main/solution/3500-3599/3518.Smallest%20Palindromic%20Rearrangement%20II/README_EN.md	Hash Table Math String Combinatorics Counting

3518. Smallest Palindromic Rearrangement II

中文文档

Description

You are given a palindromic string s and an integer k.

Return the k-th lexicographically smallest palindromic permutation of s. If there are fewer than k distinct palindromic permutations, return an empty string.

Note: Different rearrangements that yield the same palindromic string are considered identical and are counted once.

 

Example 1:

Input: s = "abba", k = 2

Output: "baab"

Explanation:

• The two distinct palindromic rearrangements of "abba" are "abba" and "baab".
• Lexicographically, "abba" comes before "baab". Since k = 2, the output is "baab".

Example 2:

Input: s = "aa", k = 2

Output: ""

Explanation:

• There is only one palindromic rearrangement: "aa".
• The output is an empty string since k = 2 exceeds the number of possible rearrangements.

Example 3:

Input: s = "bacab", k = 1

Output: "abcba"

Explanation:

• The two distinct palindromic rearrangements of "bacab" are "abcba" and "bacab".
• Lexicographically, "abcba" comes before "bacab". Since k = 1, the output is "abcba".

 

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.
• s is guaranteed to be palindromic.
• 1 <= k <= 106

Solutions

Solution 1

Python3

Java

C++

Go