Description
You are given two strings s and target, both having length n, consisting of lowercase English letters.
Return the lexicographically smallest permutation of s that is strictly greater than target. If no permutation of s is lexicographically strictly greater than target, return an empty string.
A string a is lexicographically strictly greater than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b.
Example 1:
Input: s = "abc", target = "bba"
Output: "bca"
Explanation:
- The permutations of
s(in lexicographical order) are"abc","acb","bac","bca","cab", and"cba". - The lexicographically smallest permutation that is strictly greater than
targetis"bca".
Example 2:
Input: s = "leet", target = "code"
Output: "eelt"
Explanation:
- The permutations of
s(in lexicographical order) are"eelt","eetl","elet","elte","etel","etle","leet","lete","ltee","teel","tele", and"tlee". - The lexicographically smallest permutation that is strictly greater than
targetis"eelt".
Example 3:
Input: s = "baba", target = "bbaa"
Output: ""
Explanation:
- The permutations of
s(in lexicographical order) are"aabb","abab","abba","baab","baba", and"bbaa". - None of them is lexicographically strictly greater than
target. Therefore, the answer is"".
Constraints:
1 <= s.length == target.length <= 300sandtargetconsist of only lowercase English letters.
Solutions
Same solution with better code.
/**
* @param {string} s
* @param {string} target
* @return {string}
*/
var lexGreaterPermutation = function(s, target) {
const freq = Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
freq[s.charCodeAt(i) - 97]++;
}
const fill = (str) => {
for (let i = 0; i < 26; i++) {
if (freq[i] > 0) {
str += String.fromCharCode(i + 97).repeat(freq[i]);
}
}
return str;
};
const dfs = (pos, str) => {
if (pos === target.length) {
return str > target ? str : '';
}
const start = target.charCodeAt(pos) - 97;
for (let i = start; i < 26; i++) {
if (freq[i] > 0) {
freq[i]--;
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]++;
}
}
return '';
};
return dfs(0, '');
};