日期: 2024 年 5 月 29 日

目标

给你一个仅由小写英文字母组成的字符串 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 <= 50
• s 仅由小写英文字母组成。

思路

这道题要我们求给定字符串中至少出现三次的由相同字符组成的子串的最大长度。下面分情况讨论：

• 如果特殊子串是连续的，那么取最大子串长度-2。例如：aaaa 有以下符合条件的特殊子串 (aa)aa、a(aa)a 和 aa(aa)，至少出现三次的最长特殊子字符串长度为2。
• 如果特殊子串个数为2：
  • 如果这两个子串长度相同，取长度-1。例如：aaa aaa 有以下符合条件的特殊子串 (aa)a a(aa) (aa)a a(aa)，出现了4次，最长特殊子串长度为2。
  • 如果这两个子串长度不同，取 max(last -2 , secondTolast)。例如：aa aaa aaaa 有以下符合条件的特殊子串 (aaa) (aaa)a a(aaa)，出现了3次，最长特殊子串长度为3。
• 如果特殊子串个数大于2，取max(last -2 , thirdTolast)。例如：aa aaa aaa 有以下符合条件的特殊子串 (aa) (aa)a a(aa) (aa)a a(aa)，出现了5次，最长特殊子串长度为3。

代码

/**
 * @date 2024-05-29 8:42
 */
public class MaximumLength2981 {
    public int maximumLength(String s) {
        int res = -1;
        Map<Character, List<Integer>> map = new HashMap<>(26);
        for (int i = 'a'; i <= 'z'; i++) {
            map.put((char) i, new ArrayList<>());
        }
        int n = s.length();
        char last = s.charAt(0);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == last) {
                cnt++;
            } else {
                map.get(last).add(cnt);
                cnt = 1;
                last = c;
            }
            if (i == n - 1) {
                map.get(c).add(cnt);
            }
        }
        for (Map.Entry<Character, List<Integer>> entry : map.entrySet()) {
            List<Integer> occurrence = entry.getValue();
            int size = occurrence.size();
            Collections.sort(occurrence);
            if (size >= 2) {
                Integer secondToLastOccurrence = occurrence.get(size - 2);
                Integer lastOccurrence = occurrence.get(size - 1);
                if (lastOccurrence - secondToLastOccurrence >= 1) {
                    res = Math.max(res, Math.max(secondToLastOccurrence, lastOccurrence - 2));
                } else {
                    res = Math.max(res, lastOccurrence - 1);
                }
                if (size >= 3) {
                    res = Math.max(res, Math.max(occurrence.get(size - 3), occurrence.get(size - 1) - 2));
                }
            } else if (size == 1) {
                res = Math.max(res, occurrence.get(0) - 2);
            }
        }
        return res == 0 ? -1 : res;
    }
}

性能

// todo 性能优化