Medium
题目描述
给定两个长度为 n 的字符串 s 和 target，它们都由小写英文字母组成。
返回字典序最小的 s 的排列，使其严格大于 target。如果 s 的任何排列都不严格大于 target，则返回空字符串。
字符串 a 在字典序上严格大于相同长度的字符串 b，当且仅当在第一个 a 和 b 不同的位置上，字符串 a 在字母表中的字母比字符串 b 中的相应字母更靠后。
示例 1：
输入：s = "abc", target = "bba"
输出："bca"
解释：
s 的排列（按字典序排列）是 "abc"、"acb"、"bac"、"bca"、"cab" 和 "cba"。
严格大于 target 的字典序最小排列是 "bca"。
示例 2：
输入：s = "leet", target = "code"
输出："eelt"
解释：
s 的排列（按字典序排列）是 "eelt"、"eetl"、"elet"、"elte"、"etel"、"etle"、"leet"、"lete"、"ltee"、"teel"、"tele" 和 "tlee"。
严格大于 target 的字典序最小排列是 "eelt"。
示例 3：
输入：s = "baba", target = "bbaa"
输出：""
解释：
s 的排列（按字典序排列）是 "aabb"、"abab"、"abba"、"baab"、"baba" 和 "bbaa"。
它们都不严格大于 target。因此，答案是 ""。
约束条件：
1 <= s.length == target.length <= 300s和target只包含小写英文字母
解题思路
这道题的核心思路是贪心算法配合回溯。我们需要构造字典序最小的排列，使其严格大于目标字符串。
算法步骤：
字符计数：首先统计字符串 s 中每个字符的频次，这样我们就知道有哪些字符可以使用。
逐位构造：从左到右构造结果字符串，对于每一位：
- 优先尝试与 target 相同的字符（如果可用）
- 如果不能使用相同字符，尝试使用比 target[i] 更大的最小字符
- 如果都不行，需要回溯
回溯策略：当前位置无法找到合适字符时，回溯到最近的一个可以"提升"的位置。所谓提升，就是在之前某个位置放置一个比当时选择更大的字符。
剩余字符处理：一旦在某个位置选择了比 target 对应位置更大的字符，后面的位置就可以按照字典序最小的方式排列（即按升序排列剩余字符）。
关键点：
- 贪心选择：能选择相等的就选相等的，不能选相等的就选择最小的更大字符
- 回溯时机：当前位置无法选择任何合适字符时
- 终止条件：成功构造完整字符串，或者回溯到开头仍无法找到解
代码实现
class Solution {
public:
string lexGreaterPermutation(string s, string target) {
vector<int> count(26, 0);
for (char c : s) {
count[c - 'a']++;
}
string result;
for (int i = 0; i < s.length(); i++) {
bool found = false;
// Try to use the same character as target[i]
if (count[target[i] - 'a'] > 0) {
result += target[i];
count[target[i] - 'a']--;
found = true;
} else {
// Try to use a character greater than target[i]
for (int j = target[i] - 'a' + 1; j < 26; j++) {
if (count[j] > 0) {
result += (char)('a' + j);
count[j]--;
found = true;
break;
}
}
if (found) {
// Fill the rest with smallest available characters
vector<char> remaining;
for (int j = 0; j < 26; j++) {
while (count[j] > 0) {
remaining.push_back('a' + j);
count[j]--;
}
}
sort(remaining.begin(), remaining.end());
for (char c : remaining) {
result += c;
}
return result;
}
}
if (!found) {
// Backtrack
while (!result.empty()) {
char lastChar = result.back();
result.pop_back();
count[lastChar - 'a']++;
int pos = result.length();
if (pos >= target.length()) break;
// Try to find a character greater than target[pos]
bool canUpgrade = false;
for (int j = target[pos] - 'a' + 1; j < 26; j++) {
if (count[j] > 0) {
result += (char)('a' + j);
count[j]--;
canUpgrade = true;
break;
}
}
if (canUpgrade) {
// Fill the rest with smallest available characters
vector<char> remaining;
for (int j = 0; j < 26; j++) {
while (count[j] > 0) {
remaining.push_back('a' + j);
count[j]--;
}
}
sort(remaining.begin(), remaining.end());
for (char c : remaining) {
result += c;
}
return result;
}
}
return "";
}
}
return "";
}
};
class Solution:
def lexGreaterPermutation(self, s: str, target: str) -> str:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
result = []
for i in range(len(s)):
found = False
# Try to use the same character as target[i]
target_idx = ord(target[i]) - ord('a')
if count[target_idx] > 0:
result.append(target[i])
count[target_idx] -= 1
found = True
else:
# Try to use a character greater than target[i]
for j in range(target_idx + 1, 26):
if count[j] > 0:
result.append(chr(ord('a') + j))
count[j] -= 1
found = True
break
if found:
# Fill the rest with smallest available characters
remaining = []
for j in range(26):
remaining.extend([chr(ord('a') + j)] * count[j])
remaining.sort()
result.extend(remaining)
return ''.join(result)
if not found:
# Backtrack
while result:
last_char = result.pop()
count[ord(last_char) - ord('a')] += 1
pos = len(result)
if pos >= len(target):
break
# Try to find a character greater than target[pos]
target_idx = ord(target[pos]) - ord('a')
can_upgrade = False
for j in range(target_idx + 1, 26):
if count[j] > 0:
result.append(chr(ord('a') + j))
count[j] -= 1
can_upgrade = True
break
if can_upgrade:
# Fill the rest with smallest available characters
remaining = []
for j in range(26):
remaining.extend([chr(ord('a') + j)] * count[j])
remaining.sort()
result.extend(remaining)
return ''.join(result)
return ""
return ""
public class Solution {
public string LexGreaterPermutation(string s, string target) {
int[] count = new int[26];
foreach (char c in s) {
count[c - 'a']++;
}
List<char> result = new List<char>();
for (int i = 0; i < s.Length; i++) {
bool found = false;
// Try to use the same character as target[i]
int targetIdx = target[i] - 'a';
if (count[targetIdx] > 0) {
result.Add(target[i]);
count[targetIdx]--;
found = true;
} else {
// Try to use a character greater than target[i]
for (int j = targetIdx + 1; j < 26; j++) {
if (count[j] > 0) {
result.Add((char)('a' + j));
count[j]--;
found = true;
break;
}
}
if (found) {
// Fill the rest with smallest available characters
List<char> remaining = new List<char>();
for (int j = 0; j < 26; j++) {
while (count[j] > 0) {
remaining.Add((char)('a' + j));
count[j]--;
}
}
remaining.Sort();
result.AddRange(remaining);
return new string(result.ToArray());
}
}
if (!found) {
// Backtrack
while (result.Count > 0) {
char lastChar = result[result.Count - 1];
result.RemoveAt(result.Count - 1);
count[lastChar - 'a']++;
int pos = result.Count;
if (pos >= target.Length) break;
// Try to find a character greater than target[pos]
targetIdx = target[pos] - 'a';
bool canUpgrade = false;
for (int j = targetIdx + 1; j < 26; j++) {
if (count[j] > 0) {
result.Add((char)('a' + j));
count[j]--;
canUpgrade = true;
break;
}
}
if (canUpgrade) {
// Fill the rest with smallest available characters
List<char> remaining = new List<char>();
for (int j = 0; j < 26; j++) {
while (count[j] > 0) {
remaining.Add((char)('a' + j));
count[j]--;
}
}
remaining.Sort();
result.AddRange(remaining);
return new string(result.ToArray());
}
}
return "";
}
}
return "";
}
}
var lexGreaterPermutation = function(s, target) {
const count = new Array(26).fill(0);
for (const c of s) {
count[c.charCodeAt(0) - 97]++;
}
const result = [];
for (let i = 0; i < s.length; i++) {
let found = false;
// Try to use the same character as target[i]
const targetIdx = target[i].charCodeAt(0) - 97;
if (count[targetIdx] > 0) {
result.push(target[i]);
count[targetIdx]--;
found = true;
} else {
// Try to use a character greater than target[i]
for (let j = targetIdx + 1; j < 26; j++) {
if (count[j] > 0) {
result.push(String.fromCharCode(97 + j));
count[j]--;
found = true;
break;
}
}
if (found) {
// Fill the rest with smallest available characters
const remaining = [];
for (let j = 0; j < 26; j++) {
while (count[j] > 0) {
remaining.push(String.fromCharCode(97 + j));
count[j]--;
}
}
remaining.sort();
result.push(...remaining);
return result.join('');
}
}
if (!found) {
// Backtrack
while (result.length > 0) {
const lastChar = result.pop();
count[lastChar.charCodeAt(0) - 97]++;
const pos = result.length;
if (pos >= target.length) break;
// Try to find a character greater than target[pos]
const targetIdx = target[pos].charCodeAt(0) - 97;
let canUpgrade = false;
for (let j = targetIdx + 1; j < 26; j++) {
if (count[j] > 0) {
result.push(String.fromCharCode(97 + j));
count[j]--;
canUpgrade = true;
break;
}
}
if (canUpgrade) {
// Fill the rest with smallest available characters
const remaining = [];
for (let j = 0; j < 26; j++) {
while (count[j] > 0) {
remaining.push(String.fromCharCode(97 + j));
count[j]--;
}
}
remaining.sort();
result.push(...remaining);
return result.join('');
}
}
return "";
}
}
return "";
};
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 字符计数 | O(n) | O(1) |
| 主循环 | O(n × 26) | O(n) |
| 回溯操作 | O(n²) | O(n) |
| 总体 | O(n²) | O(n) |
其中 n 是字符串长度。空间复