Description
Lexicographically Smallest Palindromic Permutation Greater Than Target
HardYou are given two strings s and target, each of length n, consisting of lowercase English letters.
Return the lexicographically smallest string that is both a palindromic permutation of s and strictly greater than target. If no such permutation exists, return an empty string.
Example 1:
Input: s = "baba", target = "abba"
Output: "baab"
Explanation:
- The palindromic permutations of
s(in lexicographical order) are"abba"and"baab". - The lexicographically smallest permutation that is strictly greater than
targetis"baab".
Example 2:
Input: s = "baba", target = "bbaa"
Output: ""
Explanation:
- The palindromic permutations of
s(in lexicographical order) are"abba"and"baab". - None of them is lexicographically strictly greater than
target. Therefore, the answer is"".
Example 3:
Input: s = "abc", target = "abb"
Output: ""
Explanation:
s has no palindromic permutations. Therefore, the answer is "".
Example 4:
Input: s = "aac", target = "abb"
Output: "aca"
Explanation:
- The only palindromic permutation of
sis"aca". "aca"is strictly greater thantarget. Therefore, the answer is"aca".
Constraints:
1 <= n == s.length == target.length <= 300sandtargetconsist of only lowercase English letters.
Solutions
Finally found and fixed the bug.
Language: javascript()DONE
CPU Performance62.76%
x
Memory Performance78.24%
x
/**
* @param {string} s
* @param {string} target
* @return {string}
*/
var lexPalindromicPermutation = function (s, target) {
if (s.length === 1 && target.length === 1 && s > target) return s;
const freq = Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
freq[s.charCodeAt(i) - 97]++;
}
let mid = '';
for (let i = 0; i < 26; i++) {
if (freq[i] & 1) {
if (mid) return '';
freq[i]--;
mid = String.fromCharCode(i + 97);
}
}
const createResponse = (str) => str + mid + str.split('').reverse().join('');
const fill = (str) => {
for (let i = 0; i < 26; i++) {
if (freq[i] > 0) {
str += String.fromCharCode(i + 97).repeat(freq[i] / 2);
}
}
return createResponse(str);
};
const targetHalfLen = Math.floor(target.length / 2);
const dfs = (pos, str) => {
if (pos === targetHalfLen) {
const full = createResponse(str);
return full > target ? full : '';
}
const start = target.charCodeAt(pos) - 97;
for (let i = start; i < 26; i++) {
if (freq[i] > 0) {
freq[i] -= 2;
const newStr = str + String.fromCharCode(i + 97);
if (i > start) {
return fill(newStr);
}
const goDeeper = dfs(pos + 1, newStr);
if (goDeeper) {
return goDeeper;
}
freq[i] += 2;
}
}
return '';
};
return dfs(0, '');
};