Medium
题目描述
给定一个长度为 n 的字符串 s 和一个整数 k，判断是否可以选择 k 个不相交的特殊子串。
特殊子串是满足以下条件的子串：
- 子串内存在的任何字符不应在字符串的其他地方出现。
- 子串不是整个字符串 s。
注意所有 k 个子串必须是不相交的，意味着它们不能重叠。
如果可以选择 k 个这样的不相交特殊子串，返回 true；否则返回 false。
示例 1：
输入：s = "abcdbaefab", k = 2
输出：true
解释：
我们可以选择两个不相交的特殊子串："cd" 和 "ef"。
"cd" 包含字符 'c' 和 'd'，它们在 s 的其他地方不出现。
"ef" 包含字符 'e' 和 'f'，它们在 s 的其他地方不出现。
示例 2：
输入：s = "cdefdc", k = 3
输出：false
解释：
最多可以有 2 个不相交的特殊子串："e" 和 "f"。由于 k = 3，输出为 false。
示例 3：
输入：s = "abeabe", k = 0
输出：true
约束条件：
- 2 <= n == s.length <= 5 * 10^4
- 0 <= k <= 26
- s 仅由小写英文字母组成。
解题思路
这道题需要找到所有可能的特殊子串，然后判断是否能选择 k 个不相交的子串。
思路分析：
理解特殊子串：特殊子串的关键是其中的字符在整个字符串中只能出现在这个子串内，不能在其他地方出现。
区间构造：对于每个字符，我们需要找到包含它的最小特殊子串。如果字符 c 在位置 i 出现，那么包含它的特殊子串必须从 c 第一次出现的位置开始，到 c 最后一次出现的位置结束。
区间合并：某些区间可能会重叠，我们需要将重叠的区间合并成一个更大的区间，因为它们不能同时被选择。
动态规划选择：得到所有可能的区间后，问题转化为：在这些区间中选择最多 k 个不相交的区间。这是一个经典的区间调度问题，可以用贪心算法解决。
算法步骤：
- 记录每个字符的第一次和最后一次出现位置
- 构造所有可能的最小特殊子串区间
- 合并重叠区间
- 使用贪心算法计算最多能选择多少个不相交区间
- 判断是否 >= k
代码实现
class Solution {
public:
bool maxSubstringLength(string s, int k) {
if (k == 0) return true;
int n = s.length();
vector<int> first(26, -1), last(26, -1);
// 记录每个字符的第一次和最后一次出现位置
for (int i = 0; i < n; i++) {
int c = s[i] - 'a';
if (first[c] == -1) first[c] = i;
last[c] = i;
}
// 构造区间
vector<pair<int, int>> intervals;
for (int c = 0; c < 26; c++) {
if (first[c] != -1 && first[c] != last[c]) {
intervals.push_back({first[c], last[c]});
}
}
if (intervals.empty()) return false;
// 按起始位置排序
sort(intervals.begin(), intervals.end());
// 合并重叠区间
vector<pair<int, int>> merged;
for (auto& interval : intervals) {
if (merged.empty() || merged.back().second < interval.first) {
merged.push_back(interval);
} else {
merged.back().second = max(merged.back().second, interval.second);
}
}
// 贪心选择最多不相交区间
sort(merged.begin(), merged.end(), [](const pair<int,int>& a, const pair<int,int>& b) {
return a.second < b.second;
});
int count = 0, lastEnd = -1;
for (auto& interval : merged) {
if (interval.first > lastEnd) {
count++;
lastEnd = interval.second;
}
}
return count >= k;
}
};
class Solution:
def maxSubstringLength(self, s: str, k: int) -> bool:
if k == 0:
return True
n = len(s)
first = [-1] * 26
last = [-1] * 26
# 记录每个字符的第一次和最后一次出现位置
for i, c in enumerate(s):
idx = ord(c) - ord('a')
if first[idx] == -1:
first[idx] = i
last[idx] = i
# 构造区间
intervals = []
for i in range(26):
if first[i] != -1 and first[i] != last[i]:
intervals.append((first[i], last[i]))
if not intervals:
return False
# 按起始位置排序
intervals.sort()
# 合并重叠区间
merged = []
for start, end in intervals:
if not merged or merged[-1][1] < start:
merged.append((start, end))
else:
merged[-1] = (merged[-1][0], max(merged[-1][1], end))
# 贪心选择最多不相交区间
merged.sort(key=lambda x: x[1])
count = 0
last_end = -1
for start, end in merged:
if start > last_end:
count += 1
last_end = end
return count >= k
public class Solution {
public bool MaxSubstringLength(string s, int k) {
if (k == 0) return true;
int n = s.Length;
int[] first = new int[26];
int[] last = new int[26];
Array.Fill(first, -1);
Array.Fill(last, -1);
// 记录每个字符的第一次和最后一次出现位置
for (int i = 0; i < n; i++) {
int c = s[i] - 'a';
if (first[c] == -1) first[c] = i;
last[c] = i;
}
// 构造区间
List<(int, int)> intervals = new List<(int, int)>();
for (int c = 0; c < 26; c++) {
if (first[c] != -1 && first[c] != last[c]) {
intervals.Add((first[c], last[c]));
}
}
if (intervals.Count == 0) return false;
// 按起始位置排序
intervals.Sort();
// 合并重叠区间
List<(int, int)> merged = new List<(int, int)>();
foreach (var interval in intervals) {
if (merged.Count == 0 || merged[merged.Count - 1].Item2 < interval.Item1) {
merged.Add(interval);
} else {
var last = merged[merged.Count - 1];
merged[merged.Count - 1] = (last.Item1, Math.Max(last.Item2, interval.Item2));
}
}
// 贪心选择最多不相交区间
merged.Sort((a, b) => a.Item2.CompareTo(b.Item2));
int count = 0, lastEnd = -1;
foreach (var interval in merged) {
if (interval.Item1 > lastEnd) {
count++;
lastEnd = interval.Item2;
}
}
return count >= k;
}
}
var maxSubstringLength = function(s, k) {
if (k === 0) return true;
const n = s.length;
const charCount = new Map();
// Count frequency of each character
for (let char of s) {
charCount.set(char, (charCount.get(char) || 0) + 1);
}
// Find all valid special substrings
const validSubstrings = [];
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
// Skip if it's the entire string
if (i === 0 && j === n - 1) continue;
const substring = s.slice(i, j + 1);
const substringChars = new Set();
let isSpecial = true;
// Check if all characters in substring don't appear outside
for (let char of substring) {
substringChars.add(char);
}
for (let char of substringChars) {
// Count occurrences of this char in the substring
let countInSubstring = 0;
for (let c of substring) {
if (c === char) countInSubstring++;
}
// If total count doesn't match substring count, char appears outside
if (charCount.get(char) !== countInSubstring) {
isSpecial = false;
break;
}
}
if (isSpecial) {
validSubstrings.push([i, j]);
}
}
}
// Sort by length (greedy approach - try longer substrings first)
validSubstrings.sort((a, b) => (b[1] - b[0]) - (a[1] - a[0]));
// Try to select k disjoint substrings using backtracking
function canSelect(index, selected, remaining) {
if (remaining === 0) return true;
if (index >= validSubstrings.length) return false;
const [start, end] = validSubstrings[index];
// Check if current substring overlaps with any selected
let overlaps = false;
for (let [selStart, selEnd] of selected) {
if (!(end < selStart || start > selEnd)) {
overlaps = true;
break;
}
}
// Try including current substring if no overlap
if (!overlaps) {
selected.push([start, end]);
if (canSelect(index + 1, selected, remaining - 1)) return true;
selected.pop();
}
// Try without current substring
return canSelect(index + 1, selected, remaining);
}
return canSelect(0, [], k);
};
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 字符位置统计 | O(n) | O(1) |
| 区间构造与排序 | O(26 log 26) | O(26) |
| 区间合并 | O(26) | O(26) |
| 贪心选择 | O(26 log 26) | O(1) |
| 总体复杂度 | O(n) | O(1) |