3妹:2哥2哥,我掐指一算,今天是你的发薪日吧, 要不要请我吃个饭哈?
2哥:切,这还用算,每个月都是10号嘛。
3妹:2哥,让我吃个瓜,能不能告诉我你的工资是多少,吓死我!
2哥:工资怎么能随便告诉别人呢,别人比你多了你难受,别人比你少了别人难受,还是不知道别人的好。
3妹:那你到底请不请吃饭嘛。
2哥:想吃饭哪那么容易,让我出一题考考你,做对了的话才可以吃~
3妹:哦耶,放马过来吧,难不倒我!
#题目:
给你一个仅由小写英文字母组成的字符串 s 。
如果一个字符串仅由单一字符组成,那么它被称为 特殊 字符串。例如,字符串 “abc” 不是特殊字符串,而字符串 “ddd”、“zz” 和 “f” 是特殊字符串。
返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度,如果不存在出现至少三次的特殊子字符串,则返回 -1 。
子字符串 是字符串中的一个连续 非空 字符序列。
示例 1:
输入:s = “aaaa”
输出:2
解释:出现三次的最长特殊子字符串是 “aa” :子字符串 “aaaa”、“aaaa” 和 “aaaa”。
可以证明最大长度是 2 。
示例 2:
输入:s = “abcdef”
输出:-1
解释:不存在出现至少三次的特殊子字符串。因此返回 -1 。
示例 3:
输入:s = “abcaba”
输出:1
解释:出现三次的最长特殊子字符串是 “a” :子字符串 “abcaba”、“abcaba” 和 “abcaba”。
可以证明最大长度是 1 。
提示:
3 <= s.length <= 5 * 10^5
s 仅由小写英文字母组成。
#思路:
分组,
按照相同字母分组,每组统计相同字母连续出现的长度。例如 aaaabbbabb 把 a 分成一组,组内有长度 4 和长度 1;把 b 分成一组,组内有长度 3 和长度 2。
单独考虑每一组,按照长度从大到小排序,设长度列表为 a。
#java代码1:
public class Solution {
public int maximumLength(String S) {
char[] s = S.toCharArray();
List<Integer>[] groups = new ArrayList[26];
Arrays.setAll(groups, i -> new ArrayList<>());
int cnt = 0;
for (int i = 0; i < s.length; i++) {
cnt++;
if (i == s.length - 1 || s[i] != s[i + 1]) {
groups[s[i] - 'a'].add(cnt); // 统计连续字符长度
cnt = 0;
}
}
int ans = 0;
for (List<Integer> a : groups) {
if (a.isEmpty()) continue;
a.sort(Collections.reverseOrder());
a.add(0);
a.add(0); // 假设还有两个空串
ans = Math.max(ans, Math.max(a.get(0) - 2, Math.max(Math.min(a.get(0) - 1, a.get(1)), a.get(2))));
}
return ans > 0 ? ans : -1;
}
}