You are given a palindromic string s and an integer k.
Return the k-thlexicographically 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.
Input: s ="abba", k =2Output: "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"`.
Input: s ="aa", k =2Output: ""Explanation:
* There is only one palindromic rearrangement:`"aa"`.* The output is an empty string since `k = 2` exceeds the number of possible rearrangements.
Input: s ="bacab", k =1Output: "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"`.
A palindrome is fully determined by its first half (and an optional middle character when length is odd). Distinct palindromes correspond to distinct permutations of the multiset formed by taking half the counts of each character from s. We can greedily build the k-th lexicographic palindrome by deciding each position of the first half: for each candidate character, count how many permutations would start with that prefix; skip whole blocks until we locate the block containing the k-th permutation.
classSolution {
funsmallestPalindrome(s: String, k: Int): String {
val cap = k.toLong() + 1val freq = IntArray(26)
for (ch in s) freq[ch - 'a']++var mid = ""for (i in0 until 26) if (freq[i] % 2==1) mid = ('a' + i).toString()
val half = IntArray(26)
var halfLen = 0for (i in0 until 26) { half[i] = freq[i] / 2; halfLen += half[i] }
funcomb(n: Int, r: Int): Long {
if (r < 0|| r > n) return0var rr = r
if (rr > n - rr) rr = n - rr
var res = 1Lfor (i in1..rr) {
res = res * (n - rr + i) / i
if (res >= cap) return cap
}
return res
}
funcountPerms(counts: IntArray, rem: Int): Long {
var ways = 1Lvar r = rem
for (c in counts) {
if (c ==0) continueval w = comb(r, c)
ways = ways * w
if (ways >= cap) return cap
r -= c
}
return ways
}
val total = countPerms(half, halfLen)
if (total < k) return""val first = StringBuilder()
var kk = k
for (pos in0 until halfLen) {
for (ch in0 until 26) {
if (half[ch] ==0) continue half[ch]--val cnt = countPerms(half, halfLen - pos - 1)
if (cnt < kk) {
kk -= cnt.toInt()
half[ch]++ } else {
first.append('a' + ch)
break }
}
}
val rev = first.toString().reversed()
return first.toString() + mid + rev
}
}
classSolution:
defsmallestPalindrome(self, s: str, k: int) -> str:
cap = k +1 freq = [0] *26for ch in s: freq[ord(ch) -97] +=1 mid =""for i in range(26):
if freq[i] %2:
mid = chr(97+ i)
half = [f //2for f in freq]
half_len = sum(half)
defcomb(n: int, r: int) -> int:
if r <0or r > n: return0 r = min(r, n - r)
res =1for i in range(1, r +1):
res = res * (n - r + i) // i
if res >= cap: return cap
return res
defcount_perms(counts: list[int], rem: int) -> int:
ways =1 r = rem
for c in counts:
if c ==0: continue w = comb(r, c)
ways = ways * w
if ways >= cap: return cap
r -= c
return ways
total = count_perms(half, half_len)
if total < k: return"" first = []
for pos in range(half_len):
for ch in range(26):
if half[ch] ==0: continue half[ch] -=1 cnt = count_perms(half, half_len - pos -1)
if cnt < k:
k -= cnt
half[ch] +=1else:
first.append(chr(97+ ch))
break ans =''.join(first)
return ans + mid + ans[::-1]