找出出现至少三次的最长特殊子字符串 I

You are given a string s that consists of lowercase English letters.

A string is called special if it is made up of only a single character. For example, the string "abc" is not special, whereas the strings "ddd", "zz", and "f" are special.

Return the length of the longest special substring of s which occurs at least thrice, or -1 if no special substring occurs at least thrice.

A substring is a contiguous non-empty sequence of characters within a string.

 

Example 1:

Input: s = "aaaa"
Output: 2
Explanation: The longest special substring which occurs thrice is "aa": substrings "aaaa", "aaaa", and "aaaa".
It can be shown that the maximum length achievable is 2.

Example 2:

Input: s = "abcdef"
Output: -1
Explanation: There exists no special substring which occurs at least thrice. Hence return -1.

Example 3:

Input: s = "abcaba"
Output: 1
Explanation: The longest special substring which occurs thrice is "a": substrings "abcaba", "abcaba", and "abcaba".
It can be shown that the maximum length achievable is 1.

 

Constraints:

• 3 <= s.length <= 50
• s consists of only lowercase English letters.

/*
 题目思路：
 1. 使用Java Stream处理字符串子串和过滤特殊字符串。
 2. 统计每个特殊子串的出现次数并记录长度。
 3. 返回满足条件的最大长度，若不存在则返回-1。
 */
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public int longestSpecialSubstring(String s) {
        int n = s.length();
        return IntStream.rangeClosed(1, n)
                .boxed()
                .flatMap(len -> IntStream.rangeClosed(0, n - len)
                        .mapToObj(i -> s.substring(i, i + len)))
                .filter(this::isSpecial)
                .collect(Collectors.groupingBy(sub -> sub, Collectors.counting()))
                .entrySet().stream()
                .filter(entry -> entry.getValue() >= 3)
                .mapToInt(entry -> entry.getKey().length())
                .max().orElse(-1);
    }

    // 检查字符串是否为特殊字符串
    private boolean isSpecial(String s) {
        char firstChar = s.charAt(0);
        return s.chars().allMatch(c -> c == firstChar);
    }
}

本题解采用哈希表记录每个字符的连续长度，从而确定是否存在符合条件的特殊子字符串。首先，初始化一个大小为26的哈希表（字典），对应于每个英文字母，用来存储该字符连续出现的长度。遍历字符串s，使用一个计数器来记录当前字符连续出现的次数。当遇到不同的字符时，将当前计数值存入相应字符的列表中，并重置计数器。遍历完成后，检查每个字符的列表，分析是否存在长度至少为3的子字符串。通过计算特定规则（如单个字符长度减2，最长两个字符长度比较等），更新可能的最长特殊子字符串长度。最后，如果没有找到符合条件的特殊子字符串，返回-1，否则返回记录的最大长度。

O(n)

O(n)