LeetCode 3458: Select K Disjoint Special Substrings (Character-Range Expansion + Interval Greedy)
LeetCode 3458StringGreedyToday we solve LeetCode 3458 - Select K Disjoint Special Substrings.
Source: https://leetcode.com/problems/select-k-disjoint-special-substrings/
English
Problem Summary
Given a string s and an integer k, determine whether we can choose at least k pairwise-disjoint special substrings. A substring is special if every character appearing inside it has all its occurrences in s fully contained in that substring.
Key Idea
A valid special substring must start at the first occurrence of its starting character. So we only try starts that are first occurrences. For each such start, we expand its right boundary to include full ranges of all characters seen inside. If during expansion we encounter a character whose first occurrence is before the start, this interval is invalid.
All valid intervals become a classic interval scheduling task: sort by right endpoint and greedily pick non-overlapping ones to maximize count.
Algorithm
1) Precompute first[26] and last[26] for every character.
2) For each index i that is first[s[i]], try to build interval [i, r]:
- initialize r = last[s[i]]
- scan j from i to r, update r = max(r, last[s[j]])
- if any first[s[j]] < i, reject this interval.
3) (If problem excludes whole string as a chosen special substring) ignore interval [0, n-1].
4) Sort all valid intervals by end, then greedily select disjoint intervals.
5) Return whether selected count is at least k.
Complexity
At most 26 candidate starts for lowercase letters, each expanded linearly over covered region. Effective complexity is O(n) in practice, plus sorting up to 26 intervals (O(1) bounded).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public boolean canSelect(String s, int k) {
if (k == 0) return true;
int n = s.length();
int[] first = new int[26];
int[] last = new int[26];
Arrays.fill(first, -1);
Arrays.fill(last, -1);
for (int i = 0; i < n; i++) {
int c = s.charAt(i) - 'a';
if (first[c] == -1) first[c] = i;
last[c] = i;
}
List<int[]> intervals = new ArrayList<>();
for (int i = 0; i < n; i++) {
int c = s.charAt(i) - 'a';
if (first[c] != i) continue;
int r = last[c];
boolean ok = true;
for (int j = i; j <= r; j++) {
int x = s.charAt(j) - 'a';
if (first[x] < i) {
ok = false;
break;
}
r = Math.max(r, last[x]);
}
if (!ok) continue;
if (i == 0 && r == n - 1) continue; // skip whole string
intervals.add(new int[]{i, r});
}
intervals.sort((a, b) -> a[1] != b[1] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
int picked = 0;
int end = -1;
for (int[] in : intervals) {
if (in[0] > end) {
picked++;
end = in[1];
if (picked >= k) return true;
}
}
return false;
}
}import "sort"
func canSelect(s string, k int) bool {
if k == 0 {
return true
}
n := len(s)
first := make([]int, 26)
last := make([]int, 26)
for i := 0; i < 26; i++ {
first[i] = -1
last[i] = -1
}
for i := 0; i < n; i++ {
c := int(s[i] - 'a')
if first[c] == -1 {
first[c] = i
}
last[c] = i
}
type interval struct{ l, r int }
arr := make([]interval, 0)
for i := 0; i < n; i++ {
c := int(s[i] - 'a')
if first[c] != i {
continue
}
r := last[c]
ok := true
for j := i; j <= r; j++ {
x := int(s[j] - 'a')
if first[x] < i {
ok = false
break
}
if last[x] > r {
r = last[x]
}
}
if !ok {
continue
}
if i == 0 && r == n-1 {
continue
}
arr = append(arr, interval{i, r})
}
sort.Slice(arr, func(i, j int) bool {
if arr[i].r != arr[j].r {
return arr[i].r < arr[j].r
}
return arr[i].l < arr[j].l
})
picked, end := 0, -1
for _, in := range arr {
if in.l > end {
picked++
end = in.r
if picked >= k {
return true
}
}
}
return false
}class Solution {
public:
bool canSelect(string s, int k) {
if (k == 0) return true;
int n = (int)s.size();
vector 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> intervals;
for (int i = 0; i < n; ++i) {
int c = s[i] - 'a';
if (first[c] != i) continue;
int r = last[c];
bool ok = true;
for (int j = i; j <= r; ++j) {
int x = s[j] - 'a';
if (first[x] < i) {
ok = false;
break;
}
r = max(r, last[x]);
}
if (!ok) continue;
if (i == 0 && r == n - 1) continue;
intervals.push_back({i, r});
}
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b){
if (a.second != b.second) return a.second < b.second;
return a.first < b.first;
});
int picked = 0, end = -1;
for (auto &in : intervals) {
if (in.first > end) {
++picked;
end = in.second;
if (picked >= k) return true;
}
}
return false;
}
}; class Solution:
def canSelect(self, s: str, k: int) -> bool:
if k == 0:
return True
n = len(s)
first = [-1] * 26
last = [-1] * 26
for i, ch in enumerate(s):
x = ord(ch) - 97
if first[x] == -1:
first[x] = i
last[x] = i
intervals = []
for i, ch in enumerate(s):
c = ord(ch) - 97
if first[c] != i:
continue
r = last[c]
ok = True
j = i
while j <= r:
x = ord(s[j]) - 97
if first[x] < i:
ok = False
break
r = max(r, last[x])
j += 1
if not ok:
continue
if i == 0 and r == n - 1:
continue
intervals.append((i, r))
intervals.sort(key=lambda p: (p[1], p[0]))
picked = 0
end = -1
for l, r in intervals:
if l > end:
picked += 1
end = r
if picked >= k:
return True
return Falsevar canSelect = function(s, k) {
if (k === 0) return true;
const n = s.length;
const first = new Array(26).fill(-1);
const last = new Array(26).fill(-1);
for (let i = 0; i < n; i++) {
const c = s.charCodeAt(i) - 97;
if (first[c] === -1) first[c] = i;
last[c] = i;
}
const intervals = [];
for (let i = 0; i < n; i++) {
const c = s.charCodeAt(i) - 97;
if (first[c] !== i) continue;
let r = last[c];
let ok = true;
for (let j = i; j <= r; j++) {
const x = s.charCodeAt(j) - 97;
if (first[x] < i) {
ok = false;
break;
}
r = Math.max(r, last[x]);
}
if (!ok) continue;
if (i === 0 && r === n - 1) continue;
intervals.push([i, r]);
}
intervals.sort((a, b) => (a[1] - b[1]) || (a[0] - b[0]));
let picked = 0;
let end = -1;
for (const [l, r] of intervals) {
if (l > end) {
picked++;
end = r;
if (picked >= k) return true;
}
}
return false;
};中文
题目概述
给定字符串 s 和整数 k，判断是否能选出至少 k 个两两不相交的“特殊子串”。特殊子串要求：子串中出现的每个字符，其在整个 s 中的出现位置都必须被该子串完整覆盖。
核心思路
合法区间一定从某个字符的首次出现位置开始。因为如果起点不是首次出现，那么该字符在左边还有出现，必然违反“完整覆盖”的定义。
因此我们只枚举“首次出现位置”作为候选起点，做区间扩展：遍历当前区间内的字符，把右边界扩成这些字符的最晚出现位置；若遇到某字符的首次出现在起点左侧，当前候选区间直接判无效。
把所有有效区间收集后，按右端点升序做贪心选不相交区间，得到可选数量上限，判断是否 >= k 即可。
算法步骤
1）预处理每个字符的首末位置 first/last。
2）枚举每个首次出现位置 i 作为候选起点并扩展区间。
3）扩展中若发现 first[x] < i，该区间非法。
4）合法区间加入列表（若题意不允许整串，过滤 [0,n-1]）。
5）区间按右端点排序，贪心挑选互不重叠区间，统计数量并比较 k。
复杂度分析
候选起点受字符种类限制（小写字母最多 26 个），总体接近线性扫描，时间复杂度可视作 O(n)，额外空间 O(1)（常数级数组 + 少量区间）。
参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public boolean canSelect(String s, int k) {
if (k == 0) return true;
int n = s.length();
int[] first = new int[26];
int[] last = new int[26];
Arrays.fill(first, -1);
Arrays.fill(last, -1);
for (int i = 0; i < n; i++) {
int c = s.charAt(i) - 'a';
if (first[c] == -1) first[c] = i;
last[c] = i;
}
List<int[]> intervals = new ArrayList<>();
for (int i = 0; i < n; i++) {
int c = s.charAt(i) - 'a';
if (first[c] != i) continue;
int r = last[c];
boolean ok = true;
for (int j = i; j <= r; j++) {
int x = s.charAt(j) - 'a';
if (first[x] < i) {
ok = false;
break;
}
r = Math.max(r, last[x]);
}
if (!ok) continue;
if (i == 0 && r == n - 1) continue; // 过滤整串
intervals.add(new int[]{i, r});
}
intervals.sort((a, b) -> a[1] != b[1] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
int picked = 0;
int end = -1;
for (int[] in : intervals) {
if (in[0] > end) {
picked++;
end = in[1];
if (picked >= k) return true;
}
}
return false;
}
}import "sort"
func canSelect(s string, k int) bool {
if k == 0 {
return true
}
n := len(s)
first := make([]int, 26)
last := make([]int, 26)
for i := 0; i < 26; i++ {
first[i] = -1
last[i] = -1
}
for i := 0; i < n; i++ {
c := int(s[i] - 'a')
if first[c] == -1 {
first[c] = i
}
last[c] = i
}
type interval struct{ l, r int }
arr := make([]interval, 0)
for i := 0; i < n; i++ {
c := int(s[i] - 'a')
if first[c] != i {
continue
}
r := last[c]
ok := true
for j := i; j <= r; j++ {
x := int(s[j] - 'a')
if first[x] < i {
ok = false
break
}
if last[x] > r {
r = last[x]
}
}
if !ok {
continue
}
if i == 0 && r == n-1 {
continue
}
arr = append(arr, interval{i, r})
}
sort.Slice(arr, func(i, j int) bool {
if arr[i].r != arr[j].r {
return arr[i].r < arr[j].r
}
return arr[i].l < arr[j].l
})
picked, end := 0, -1
for _, in := range arr {
if in.l > end {
picked++
end = in.r
if picked >= k {
return true
}
}
}
return false
}class Solution {
public:
bool canSelect(string s, int k) {
if (k == 0) return true;
int n = (int)s.size();
vector 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> intervals;
for (int i = 0; i < n; ++i) {
int c = s[i] - 'a';
if (first[c] != i) continue;
int r = last[c];
bool ok = true;
for (int j = i; j <= r; ++j) {
int x = s[j] - 'a';
if (first[x] < i) {
ok = false;
break;
}
r = max(r, last[x]);
}
if (!ok) continue;
if (i == 0 && r == n - 1) continue;
intervals.push_back({i, r});
}
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b){
if (a.second != b.second) return a.second < b.second;
return a.first < b.first;
});
int picked = 0, end = -1;
for (auto &in : intervals) {
if (in.first > end) {
++picked;
end = in.second;
if (picked >= k) return true;
}
}
return false;
}
}; class Solution:
def canSelect(self, s: str, k: int) -> bool:
if k == 0:
return True
n = len(s)
first = [-1] * 26
last = [-1] * 26
for i, ch in enumerate(s):
x = ord(ch) - 97
if first[x] == -1:
first[x] = i
last[x] = i
intervals = []
for i, ch in enumerate(s):
c = ord(ch) - 97
if first[c] != i:
continue
r = last[c]
ok = True
j = i
while j <= r:
x = ord(s[j]) - 97
if first[x] < i:
ok = False
break
r = max(r, last[x])
j += 1
if not ok:
continue
if i == 0 and r == n - 1:
continue
intervals.append((i, r))
intervals.sort(key=lambda p: (p[1], p[0]))
picked = 0
end = -1
for l, r in intervals:
if l > end:
picked += 1
end = r
if picked >= k:
return True
return Falsevar canSelect = function(s, k) {
if (k === 0) return true;
const n = s.length;
const first = new Array(26).fill(-1);
const last = new Array(26).fill(-1);
for (let i = 0; i < n; i++) {
const c = s.charCodeAt(i) - 97;
if (first[c] === -1) first[c] = i;
last[c] = i;
}
const intervals = [];
for (let i = 0; i < n; i++) {
const c = s.charCodeAt(i) - 97;
if (first[c] !== i) continue;
let r = last[c];
let ok = true;
for (let j = i; j <= r; j++) {
const x = s.charCodeAt(j) - 97;
if (first[x] < i) {
ok = false;
break;
}
r = Math.max(r, last[x]);
}
if (!ok) continue;
if (i === 0 && r === n - 1) continue;
intervals.push([i, r]);
}
intervals.sort((a, b) => (a[1] - b[1]) || (a[0] - b[0]));
let picked = 0;
let end = -1;
for (const [l, r] of intervals) {
if (l > end) {
picked++;
end = r;
if (picked >= k) return true;
}
}
return false;
};
Comments