Medium

题目描述

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

解题思路

这道题需要找出现至少三次的最长特殊子字符串。特殊子字符串指的是只由单一字符组成的字符串。

解题思路：

  1. 统计连续字符段：遍历字符串，统计每个字符的连续出现长度。例如 “aaabba” 中，字符 ‘a’ 有长度为3和1的连续段，字符 ‘b’ 有长度为2的连续段。

  2. 分组管理：按字符分组，每组维护该字符所有连续段的长度列表。对于每个字符，我们只需要保存前3个最长的连续段长度。

  3. 计算贡献：对于长度为 L 的连续段，它可以贡献：

    • 1个长度为L的子字符串
    • 2个长度为L-1的子字符串
    • 3个长度为L-2的子字符串
    • …
    • L个长度为1的子字符串

  4. 寻找答案：对于每个字符组，找出能出现至少3次的最大长度。这可以通过维护前3大的连续段长度来高效计算。

优化策略：

  • 使用哈希表存储每个字符的前3大连续段长度
  • 动态维护这个前3大列表，避免完整排序
  • 根据前3大长度直接计算能达到的最大长度

时间复杂度为 O(n)，空间复杂度为 O(1)，因为最多只有26个字母，每个字母最多存储3个长度值。

代码实现

class Solution {
public:
    int maximumLength(string s) {
        vector<vector<int>> groups(26);
        int n = s.length();
        
        // 统计每个字符的连续段长度
        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && s[j] == s[i]) {
                j++;
            }
            int len = j - i;
            int ch = s[i] - 'a';
            
            // 只保留前3大的长度
            groups[ch].push_back(len);
            sort(groups[ch].rbegin(), groups[ch].rend());
            if (groups[ch].size() > 3) {
                groups[ch].pop_back();
            }
            
            i = j;
        }
        
        int result = -1;
        
        // 对每个字符组计算最大可能长度
        for (int ch = 0; ch < 26; ch++) {
            if (groups[ch].empty()) continue;
            
            vector<int>& lens = groups[ch];
            
            // 补齐到3个元素，不足的用0填充
            while (lens.size() < 3) {
                lens.push_back(0);
            }
            
            // 计算能出现至少3次的最大长度
            // 情况1：第一长的段贡献3次 (len-2)
            if (lens[0] >= 3) {
                result = max(result, lens[0] - 2);
            }
            
            // 情况2：第一长的段贡献2次，第二长的段贡献1次
            if (lens[0] >= 2 && lens[1] >= 1) {
                result = max(result, min(lens[0] - 1, lens[1]));
            }
            
            // 情况3：三个段各贡献1次
            if (lens[2] >= 1) {
                result = max(result, lens[2]);
            }
        }
        
        return result;
    }
};

class Solution:
    def maximumLength(self, s: str) -> int:
        groups = [[] for _ in range(26)]
        n = len(s)
        
        # 统计每个字符的连续段长度
        i = 0
        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
            length = j - i
            ch = ord(s[i]) - ord('a')
            
            # 只保留前3大的长度
            groups[ch].append(length)
            groups[ch].sort(reverse=True)
            if len(groups[ch]) > 3:
                groups[ch].pop()
            
            i = j
        
        result = -1
        
        # 对每个字符组计算最大可能长度
        for ch in range(26):
            if not groups[ch]:
                continue
            
            lens = groups[ch]
            
            # 补齐到3个元素，不足的用0填充
            while len(lens) < 3:
                lens.append(0)
            
            # 计算能出现至少3次的最大长度
            # 情况1：第一长的段贡献3次 (len-2)
            if lens[0] >= 3:
                result = max(result, lens[0] - 2)
            
            # 情况2：第一长的段贡献2次，第二长的段贡献1次
            if lens[0] >= 2 and lens[1] >= 1:
                result = max(result, min(lens[0] - 1, lens[1]))
            
            # 情况3：三个段各贡献1次
            if lens[2] >= 1:
                result = max(result, lens[2])
        
        return result

public class Solution {
    public int MaximumLength(string s) {
        List<int>[] groups = new List<int>[26];
        for (int i = 0; i < 26; i++) {
            groups[i] = new List<int>();
        }
        
        int n = s.Length;
        
        // 统计每个字符的连续段长度
        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && s[j] == s[i]) {
                j++;
            }
            int length = j - i;
            int ch = s[i] - 'a';
            
            // 只保留前3大的长度
            groups[ch].Add(length);
            groups[ch].Sort((a, b) => b.CompareTo(a));
            if (groups[ch].Count > 3) {
                groups[ch].RemoveAt(groups[ch].Count - 1);
            }
            
            i = j;
        }
        
        int result = -1;
        
        // 对每个字符组计算最大可能长度
        for (int ch = 0; ch < 26; ch++) {
            if (groups[ch].Count == 0) continue;
            
            var lens = groups[ch];
            
            // 补齐到3个元素，不足的用0填充
            while (lens.Count < 3) {
                lens.Add(0);
            }
            
            // 计算能出现至少3次的最大长度
            // 情况1：第一长的段贡献3次 (len-2)
            if (lens[0] >= 3) {
                result = Math.Max(result, lens[0] - 2);
            }
            
            // 情况2：第一长的段贡献2次，第二长的段贡献1次
            if (lens[0] >= 2 && lens[1] >= 1) {
                result = Math.Max(result, Math.Min(lens[0] - 1, lens[1]));
            }
            
            // 情况3：三个段各贡献1次
            if (lens[2] >= 1) {
                result = Math.Max(result, lens[2]);
            }
        }
        
        return result;
    }
}

var maximumLength = function(s) {
    const groups = Array.from({length: 26}, () => []);
    const n = s.length;
    
    // 统计每个字符的连续段长度
    for (let i = 0; i < n; ) {
        let j = i;
        while (j < n && s[j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)遍历字符串一次，每个字符最多处理常数次
空间复杂度O(1)最多存储26个字母，每个字母最多3个长度值

相关题目