【教3妹学编程-算法题】找出出现至少三次的最长特殊子字符串 II
source link: https://blog.51cto.com/u_6813689/9201673
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
【教3妹学编程-算法题】找出出现至少三次的最长特殊子字符串 II
精选 原创
3妹：2哥2哥，我掐指一算，今天是你的发薪日吧， 要不要请我吃个饭哈？ 2哥：切，这还用算，每个月都是10号嘛。 3妹：2哥，让我吃个瓜，能不能告诉我你的工资是多少，吓死我！ 2哥：工资怎么能随便告诉别人呢，别人比你多了你难受，别人比你少了别人难受，还是不知道别人的好。 3妹：那你到底请不请吃饭嘛。 2哥：想吃饭哪那么容易，让我出一题考考你，做对了的话才可以吃~ 3妹：哦耶，放马过来吧，难不倒我！
#题目： 给你一个仅由小写英文字母组成的字符串 s 。
如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -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;
}
}Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK