class Solution {
public:
vector<string> maxNumOfSubstrings(string s) {
}
};
1520. 最多的不重叠子字符串
给你一个只包含小写字母的字符串 s ，你需要找到 s 中最多数目的非空子字符串，满足如下条件：
s[i..j] 和 s[x..y] ，要么 j < x 要么 i > y 。char ，那么 s 中所有 char 字符都应该在这个子字符串中。请你找到满足上述条件的最多子字符串数目。如果有多个解法有相同的子字符串数目，请返回这些子字符串总长度最小的一个解。可以证明最小总长度解是唯一的。
请注意，你可以以 任意 顺序返回最优解的子字符串。
示例 1：
输入：s = "adefaddaccc" 输出：["e","f","ccc"] 解释：下面为所有满足第二个条件的子字符串： [ "adefaddaccc" "adefadda", "ef", "e", "f", "ccc", ] 如果我们选择第一个字符串，那么我们无法再选择其他任何字符串，所以答案为 1 。如果我们选择 "adefadda" ，剩下子字符串中我们只可以选择 "ccc" ，它是唯一不重叠的子字符串，所以答案为 2 。同时我们可以发现，选择 "ef" 不是最优的，因为它可以被拆分成 2 个子字符串。所以最优解是选择 ["e","f","ccc"] ，答案为 3 。不存在别的相同数目子字符串解。
示例 2：
输入：s = "abbaccd" 输出：["d","bb","cc"] 解释：注意到解 ["d","abba","cc"] 答案也为 3 ，但它不是最优解，因为它的总长度更长。
提示：
1 <= s.length <= 10^5s 只包含小写英文字母。原站题解
golang 解法, 执行用时: 16 ms, 内存消耗: 6.7 MB, 提交时间: 2023-09-05 22:24:58
// https://www.bilibili.com/video/BV1yz4y1D7p3
func min(i, j int) int { if i < j { return i }; return j }
func max(i, j int) int { if i > j { return i }; return j}
func maxNumOfSubstrings(s string) []string {
count := len(s)
left := make([]int, 26)
right := make([]int, 26)
for i := 0; i < 26; i++ {
left[i] = math.MaxInt32
}
for i := 0; i < 26; i++ {
right[i] = math.MinInt32
}
for i := 0; i < count; i++ {
left[s[i]-'a'] = min(i, left[s[i]-'a'])
right[s[i]-'a'] = max(i, right[s[i]-'a'])
}
// 关键函数 extend
//计算从第i个字母开始，满足条件的子串的右边边界,left 表示某个字母第一次出现的位置,right 表示某个字母最后一次出现的位置
//保证下一次迭代，如果有相交，肯定是上一次迭代的子串
extend := func(i int) int {
p := right[s[i]-'a'] //最后出现的位置
pos := i
for pos < p {
if left[s[pos]-'a'] < i {
return -1
}
if right[s[pos]-'a'] > p {
p = right[s[pos]-'a']
}
pos++
}
return p
}
res := make([]string, 0)
last := -1
for i := 0; i < count; i++ {
// 只计算当前字母第一次出现的位置
if i != left[s[i]-'a'] {
continue
}
p := extend(i)
if p == -1 {
continue
}
if i > last {
res = append(res, s[i:p+1])
} else {
res[len(res)-1] = s[i : p+1]
}
last = p
}
return res
}
java 解法, 执行用时: 42 ms, 内存消耗: 43.8 MB, 提交时间: 2023-09-05 22:23:34
class Solution {
public List<String> maxNumOfSubstrings(String s) {
Seg[] seg = new Seg[26];
for (int i = 0; i < 26; ++i) {
seg[i] = new Seg(-1, -1);
}
// 预处理左右端点
for (int i = 0; i < s.length(); ++i) {
int char_idx = s.charAt(i) - 'a';
if (seg[char_idx].left == -1) {
seg[char_idx].left = seg[char_idx].right = i;
} else {
seg[char_idx].right = i;
}
}
for (int i = 0; i < 26; ++i) {
if (seg[i].left != -1) {
for (int j = seg[i].left; j <= seg[i].right; ++j) {
int char_idx = s.charAt(j) - 'a';
if (seg[i].left <= seg[char_idx].left && seg[char_idx].right <= seg[i].right) {
continue;
}
seg[i].left = Math.min(seg[i].left, seg[char_idx].left);
seg[i].right = Math.max(seg[i].right, seg[char_idx].right);
j = seg[i].left;
}
}
}
// 贪心选取
Arrays.sort(seg);
List<String> ans = new ArrayList<String>();
int end = -1;
for (Seg segment : seg) {
int left = segment.left, right = segment.right;
if (left == -1) {
continue;
}
if (end == -1 || left > end) {
end = right;
ans.add(s.substring(left, right + 1));
}
}
return ans;
}
class Seg implements Comparable<Seg> {
int left, right;
public Seg(int left, int right) {
this.left = left;
this.right = right;
}
public int compareTo(Seg rhs) {
if (right == rhs.right) {
return rhs.left - left;
}
return right - rhs.right;
}
}
}
python3 解法, 执行用时: 3212 ms, 内存消耗: 17 MB, 提交时间: 2023-09-05 22:23:20
class Seg:
def __init__(self, left=-1, right=-1):
self.left = left
self.right = right
def __lt__(self, rhs):
return self.left > rhs.left if self.right == rhs.right else self.right < rhs.right
class Solution:
def maxNumOfSubstrings(self, s: str) -> List[str]:
seg = [Seg() for _ in range(26)]
# 预处理左右端点
for i in range(len(s)):
charIdx = ord(s[i]) - ord('a')
if seg[charIdx].left == -1:
seg[charIdx].left = seg[charIdx].right = i
else:
seg[charIdx].right = i
for i in range(26):
if seg[i].left != -1:
j = seg[i].left
while j <= seg[i].right:
charIdx = ord(s[j]) - ord('a')
if seg[i].left <= seg[charIdx].left and seg[charIdx].right <= seg[i].right:
pass
else:
seg[i].left = min(seg[i].left, seg[charIdx].left)
seg[i].right = max(seg[i].right, seg[charIdx].right)
j = seg[i].left
j += 1
# 贪心选取
seg.sort()
ans = list()
end = -1
for segment in seg:
left, right = segment.left, segment.right
if left == -1:
continue
if end == -1 or left > end:
end = right
ans.append(s[left:right+1])
return ans