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 <= 50
  • s 仅由小写英文字母组成。

解题思路

解题思路

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

方法一：暴力枚举（推荐）

由于数据规模较小（字符串长度最多50），我们可以使用暴力方法：

  1. 枚举所有可能的子字符串
  2. 检查每个子字符串是否为特殊字符串（只包含单一字符）
  3. 统计每个特殊子字符串的出现次数
  4. 找到出现至少三次的最长特殊子字符串

方法二：优化统计

我们可以先统计每个字符的连续段长度，然后对每个字符计算能形成的特殊子字符串数量：

  • 对于长度为 n 的连续段，可以形成长度为 1 的子字符串 n 个，长度为 2 的子字符串 (n-1) 个，以此类推
  • 然后检查每种长度的特殊子字符串是否出现至少 3 次

两种方法在小数据规模下性能差异不大，但第一种方法更直观易懂。

代码实现

class Solution {
public:
    int maximumLength(string s) {
        unordered_map<string, int> count;
        int n = s.length();
        
        // 枚举所有子字符串
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                string sub = s.substr(i, j - i + 1);
                // 检查是否为特殊字符串（所有字符相同）
                bool isSpecial = true;
                for (int k = 1; k < sub.length(); k++) {
                    if (sub[k] != sub[0]) {
                        isSpecial = false;
                        break;
                    }
                }
                if (isSpecial) {
                    count[sub]++;
                }
            }
        }
        
        int maxLen = -1;
        for (auto& pair : count) {
            if (pair.second >= 3) {
                maxLen = max(maxLen, (int)pair.first.length());
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def maximumLength(self, s: str) -> int:
        count = {}
        n = len(s)
        
        # 枚举所有子字符串
        for i in range(n):
            for j in range(i, n):
                sub = s[i:j+1]
                # 检查是否为特殊字符串（所有字符相同）
                if len(set(sub)) == 1:
                    count[sub] = count.get(sub, 0) + 1
        
        max_len = -1
        for sub, freq in count.items():
            if freq >= 3:
                max_len = max(max_len, len(sub))
        
        return max_len

public class Solution {
    public int MaximumLength(string s) {
        Dictionary<string, int> count = new Dictionary<string, int>();
        int n = s.Length;
        
        // 枚举所有子字符串
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                string sub = s.Substring(i, j - i + 1);
                // 检查是否为特殊字符串（所有字符相同）
                bool isSpecial = true;
                for (int k = 1; k < sub.Length; k++) {
                    if (sub[k] != sub[0]) {
                        isSpecial = false;
                        break;
                    }
                }
                if (isSpecial) {
                    count[sub] = count.GetValueOrDefault(sub, 0) + 1;
                }
            }
        }
        
        int maxLen = -1;
        foreach (var pair in count) {
            if (pair.Value >= 3) {
                maxLen = Math.Max(maxLen, pair.Key.Length);
            }
        }
        
        return maxLen;
    }
}

var maximumLength = function(s) {
    const n = s.length;
    const count = new Map();
    
    // Generate all special substrings and count their occurrences
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            if (s[j] !== s[i]) break;
            const substring = s.substring(i, j + 1);
            count.set(substring, (count.get(substring) || 0) + 1);
        }
    }
    
    let maxLength = -1;
    
    // Find the longest special substring that occurs at least 3 times
    for (const [substring, freq] of count) {
        if (freq >= 3) {
            maxLength = Math.max(maxLength, substring.length);
        }
    }
    
    return maxLength;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n³)，其中 n 是字符串长度。枚举所有子字符串需要 O(n²)，检查每个子字符串是否为特殊字符串需要 O(n)。
空间复杂度O(n³)，最坏情况下所有子字符串都是特殊字符串，需要存储在哈希表中。

相关题目