Easy

题目描述

给定一个字符串 s，返回满足每个字符最多出现两次的最长子字符串的长度。

示例 1：

输入：s = "bcbbbcba"
输出：4
解释：子字符串 "bcbb" 长度为 4，且每个字符最多出现两次。

示例 2：

输入：s = "aaaa"
输出：2
解释：子字符串 "aa" 长度为 2，且每个字符最多出现两次。

约束条件：

  • 2 <= s.length <= 100
  • s 仅由小写英文字母组成

提示：

  • 由于约束条件很小，我们可以通过暴力枚举所有子字符串。

解题思路

解题思路

本题要求找到满足每个字符最多出现两次的最长子字符串。由于字符串长度最大为100，可以考虑以下两种解法：

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

枚举所有可能的子字符串，对每个子字符串统计字符频次，如果所有字符的出现次数都不超过2，则更新最大长度。时间复杂度为O(n³)，但由于n≤100，完全可以接受。

方法二：滑动窗口优化

使用哈希表记录当前窗口中每个字符的出现次数。右指针不断扩展窗口，当某个字符出现次数超过2时，移动左指针缩小窗口，直到该字符次数不超过2。这种方法时间复杂度为O(n)。

两种方法都能有效解决问题，考虑到代码简洁性，推荐使用暴力枚举法。

代码实现

class Solution {
public:
    int maximumLengthSubstring(string s) {
        int n = s.length();
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            unordered_map<char, int> count;
            for (int j = i; j < n; j++) {
                count[s[j]]++;
                if (count[s[j]] > 2) {
                    break;
                }
                maxLen = max(maxLen, j - i + 1);
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        n = len(s)
        max_len = 0
        
        for i in range(n):
            count = {}
            for j in range(i, n):
                count[s[j]] = count.get(s[j], 0) + 1
                if count[s[j]] > 2:
                    break
                max_len = max(max_len, j - i + 1)
        
        return max_len

public class Solution {
    public int MaximumLengthSubstring(string s) {
        int n = s.Length;
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            Dictionary<char, int> count = new Dictionary<char, int>();
            for (int j = i; j < n; j++) {
                if (count.ContainsKey(s[j])) {
                    count[s[j]]++;
                } else {
                    count[s[j]] = 1;
                }
                
                if (count[s[j]] > 2) {
                    break;
                }
                maxLen = Math.Max(maxLen, j - i + 1);
            }
        }
        
        return maxLen;
    }
}

var maximumLengthSubstring = function(s) {
    const n = s.length;
    let maxLen = 0;
    
    for (let i = 0; i < n; i++) {
        const count = {};
        for (let j = i; j < n; j++) {
            count[s[j]] = (count[s[j]] || 0) + 1;
            if (count[s[j]] > 2) {
                break;
            }
            maxLen = Math.max(maxLen, j - i + 1);
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
暴力枚举O(n²)O(1)
滑动窗口O(n)O(1)

注：空间复杂度为O(1)是因为字符集大小固定为26个小写字母。