Smallest Palindromic Rearrangement II
Real-world version: The k-th Mirrored RearrangementThe statement here is our own: the same inputs, outputs and technique.
A tag reads s, and the tag is already the same read either way.
Consider every rearrangement of the tag's letters that also reads the same either way, counting each distinct rearrangement once. List them in dictionary order.
Return the k-th one, or the empty string when fewer than k exist.
Examples
Example 1
- Input
- s = "abcba", k = 4
- Output
- ""
The front half holds one a and one b, so the halves in order are "ab" and "ba", giving only two rearrangements. There is no fourth, so nothing is returned.
Example 2
- Input
- s = "abcba", k = 1
- Output
- "abcba"
The smallest front half is "ab", the middle letter is the odd one out, and mirroring the half gives back the tag itself.
Example 3
- Input
- s = "aabbaa", k = 3
- Output
- "baaaab"
The front half holds two a and one b, so the halves in order are "aab", "aba" and "baa"; the third mirrors into this tag.
Constraints
- 1 <= s.length <= 10^4
- s consists of lowercase English letters only
- s reads the same either way
- 1 <= k <= 10^6
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def smallest_palindrome(s: str, k: int) -> str:public String smallestPalindrome(String s, int k)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 13 test cases: 13 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's