【教3妹学编程-算法题】找出出现至少三次的最长特殊子字符串 II

发布时间:2024年01月11日

开心

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;
    }
}
文章来源:https://blog.csdn.net/kangbin825/article/details/135534819
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。