Leetcode每日一题 —— 1520. 最多的不重叠子字符串

力扣 LeetCode

1520. 最多的不重叠子字符串 - 力扣（LeetCode）

1520. 最多的不重叠子字符串 - 给你一个只包含小写字母的字符串 s ，你需要找到 s 中最多数目的非空子字符串，满足如下条件：

1. 这些字符串之间互不重叠，也就是说对于任意两个子字符串 s[i..j] 和 s[x..y] ，要么 j < x 要么 i > y 。
2. 如果一个子字符串包含字符 char ，那么 s 中所有 char...

思路

朴素思路

- 先从左到右、从右到左分别遍历一遍，记录每种字母出现的第一个、最后一个和中间夹杂的其他字母。

- 遍历26个字母，如果字母的范围内夹杂了其他字母，那么更新范围，直到不再变动位置。

- 按范围从小到大排序并遍历，取与之前选中字符串不重叠的字符串加入到结果中。

PS

朴素、低效且丑陋

代码```
class Solution {
public List<String> maxNumOfSubstrings(String s) {
int[] chars = new int[s.length()];
for (int i = 0; i < chars.length; i++) {
chars[i] = s.charAt(i) - 'a';
}
int[] first = new int[26];
int[] last = new int[26];
HashSet<Integer>[] sets = new HashSet[26];
Arrays.fill(first, -1);
Arrays.fill(last, -1);
for (int i = 0; i < 26; i++) {
sets[i] = new HashSet<>();
}
for (int i = chars.length - 1; i>= 0; i--) {
if (last[chars[i]] == -1) {
last[chars[i]] = i;
}
}
for (int i = 0; i < chars.length; i++) {
if (first[chars[i]] == -1) {
first[chars[i]] = i;
}
for (int j = 0; j < 26; j++) {
if (first[j] != -1 && last[j] > i) {
sets[j].add(chars[i]);
}
}
}
boolean changed = false;
do {
changed = false;
for (int i = 0; i < 26; i++) {
for (Integer j : sets[i]) {
if (first[i] > first[j]) {
first[i] = first[j];
changed = true;
}
if (last[i] < last[j]) {
last[i] = last[j];
changed = true;
}
}
}
} while (changed);
List<int[]> rec = new ArrayList<>();
for (int i = 0; i < 26; i++) {
if (first[i] != -1) {
rec.add(new int[]{last[i] - first[i] + 1, first[i], last[i]});
}
}
rec.sort((a, b) -> a[0] - b[0]);
boolean[] vis = new boolean[rec.size()];
for (int i = 0; i < rec.size(); i++) {
int[] r = rec.get(i);
boolean v = true;
for (int j = 0; j < i; j++) {
if (!vis[j]) {
continue;
}
int[] t = rec.get(j);
if (r[1] <= t[1] && r[2] >= t[1]) {
v = false;
break;
}
}
if (v) {
vis[i] = true;
}
}
List<String> result = new ArrayList<>();
for (int i = 0; i < vis.length; i++) {
if (vis[i]) {
int[] r = rec.get(i);
result.add(s.substring(r[1], r[2] + 1));
}
}
return result;
}
}