Leetcode 2981. 找出出现至少三次的最长特殊子字符串 I
给你一个仅由小写英文字母组成的字符串 s 。
如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 “abc” 不是特殊字符串，而字符串 “ddd”、“zz” 和 “f” 是特殊字符串。
返回在 s 中出现 至少三次 的 最长特殊子字符串的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。
子字符串 是字符串中的一个连续 非空 字符序列。
首先需要明确两个概念：
- 特殊字符串：只有单一字符组成的字符串。
- 出现：这里是可以是可以重复，比如 “aaa”，出现两次是：前两个字符一次，后两个字符一次。
对于一个长度为 n 的特殊字符串：
- 出现一次的最长长度为 n；
- 出现两次的最长长度为 n - 1；
- 出现三次的最长长度为 n - 2；
- 出现 m 次的最长长度为 n -m - 1 (m < n)。
出现三次的特殊字符串，最理想的情况，是这个特殊字符串出现字符串中的三处地方（中间是有其他字符隔开的），比如 “aabaabaa”，那么就可以提取每段，就是出现三次，这种情况下最长长度就是每段出现一次，最长长度就是最短的那段的长度。
但是并不是分为三段，也有可能是两段，这时，要想获得最长长度，让更长的那段中出现两次，更短的那段出现一次。
当然还有一种情况就是只有一段，那么就必须让这段出现三次才能获取到最长长度。
字符串中会出现多段：
- 如果考虑只在一段中找到最长长度，最长长度是 n - 2，那选择在最长的那段中找到；
- 如果考虑在两段中找到最长长度，最长长度是让更长的那段出现两次 n - 1，另一段出现一次 n，那选择最长的两段中找到结果；
- 如果考虑在三段中找到最长长度，最长长度就是每段出现一次，最长长度就是最短那段的长度；
- 如果考虑在大于三段中找到最长长度，选择其中的三段进行考虑，那么就是选择最长的三段考虑得到最长长度。因此，只需要保存最长三段的长度即可。
有三段，可能考虑三段不是最优结果，也有可能考虑两段的时候结果更好哟！！也有可能是一段哟！！！
用一个数组保存每个字母每段的长度，题中说明字符串都是小写字母，并且只需要保存最长的三段（保持递增更好计算哦），因此使用一个 26 * 4 的数组（保存最长的三段使用 *4 的原因后续说明）。
首先统计每段特殊字符串的长度，一个字符也需要考虑哦：
int i = 0
while (i < len) {
int cnt = 1; // 特殊字符串长度
char c = s.charAt(i);
while ((i < len - 1) && (s.charAt(i + 1) == c)) {
i++;
cnt++;
}
i++;
}
保存数据，每次将数据插入到最后一个位置，从后往前冒泡使其放入正确的位置保持递增，因此才使用 *4。
// 冒泡排序插入
list[c - 'a'][3] = cnt;
for (int j = 2; j >= 0; j--) {
if (list[c - 'a'][j] < list[c - 'a'][j + 1]) {
int tmp = list[c - 'a'][j + 1];
list[c - 'a'][j + 1] = list[c - 'a'][j];
list[c- 'a'][j] = tmp;
} else {
break;
}
}
最后传入每个字母组成的的特殊字符串数组，进行判断得到最长长度
/**
* 一个长度为 n 的字符串
* 出现一次最长长度为 n
* 出现两次最长长度为 n - 1
* 出现三次最长长度为 n - 2
*/
public int maxLength(int[] list) {
if (list[0] == 0) return -1; // 字母没有出现
int res = list[0] - 2; // 考虑一段
if (list[1] != 0) { // 考虑两段
int tmp = list[0] - 1;
tmp = Math.min(tmp, list[1]);
res = Math.max(tmp, res);
}
if (list[2] != 0) { // 考虑三段
res = Math.max(res, list[2]);
}
if (res <= 0) return -1; // 无效返回 -1
return res;
}
完整代码：
class Solution {
public int maximumLength(String s) {
int[][] list = new int[26][4];
int len = s.length();
int i = 0;
while (i < len) {
int cnt = 1; // 特殊字符串长度
char c = s.charAt(i);
while ((i < len - 1) && (s.charAt(i + 1) == c)) {
i++;
cnt++;
}
i++;
// 冒泡排序插入
list[c - 'a'][3] = cnt;
for (int j = 2; j >= 0; j--) {
if (list[c - 'a'][j] < list[c - 'a'][j + 1]) {
int tmp = list[c - 'a'][j + 1];
list[c - 'a'][j + 1] = list[c - 'a'][j];
list[c- 'a'][j] = tmp;
} else {
break;
}
}
}
int res = -1;
for (i = 0; i < 26; i++) {
res = Math.max(res, maxLength(list[i]));
}
return res;
}
/**
* 一个长度为 n 的字符串
* 出现一次最长长度为 n
* 出现两次最长长度为 n - 1
* 出现三次最长长度为 n - 2
*/
public int maxLength(int[] list) {
if (list[0] == 0) return -1;
int res = list[0] - 2;
if (list[1] != 0) {
int tmp = list[0] - 1;
tmp = Math.min(tmp, list[1]);
res = Math.max(tmp, res);
}
if (list[2] != 0) {
res = Math.max(res, list[2]);
}
if (res <= 0) return -1;
return res;
}
}
