Medium

题目描述

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

如果不存在这样的子字符串，则返回 0。

示例 1：

输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。

示例 2：

输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

提示：

  • 1 <= s.length <= 10^4
  • s 只含有小写英文字母
  • 1 <= k <= 10^5

解题思路

这道题有三种主要解法：

1. 分治法（推荐） 核心思想是如果字符串中某个字符出现次数小于k，那么包含这个字符的任何子串都不可能满足条件。因此我们可以用这样的字符作为分割点，将字符串分割成多个子问题递归求解。

2. 滑动窗口 枚举子串中不同字符的个数（1到26），对于每个固定的字符种类数，使用滑动窗口找到最长的满足条件的子串。

3. 暴力枚举 枚举所有可能的子串，检查每个子串是否满足条件，时间复杂度较高。

分治法的优势在于能够有效剪枝，平均情况下性能最佳。算法步骤：

  1. 统计字符串中每个字符的出现次数
  2. 找到第一个出现次数小于k的字符作为分割点
  3. 如果没有这样的字符，说明整个字符串满足条件
  4. 否则以该字符为分界点分割字符串，递归处理各个子段
  5. 返回所有子段结果的最大值

代码实现

class Solution {
public:
    int longestSubstring(string s, int k) {
        return divide(s, k);
    }
    
private:
    int divide(string s, int k) {
        if (s.length() < k) return 0;
        
        // 统计字符频次
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }
        
        // 找到第一个不满足条件的字符
        for (int i = 0; i < s.length(); i++) {
            if (count[s[i] - 'a'] < k) {
                int maxLen = 0;
                int start = 0;
                // 以不满足条件的字符为分割点
                for (int j = 0; j <= s.length(); j++) {
                    if (j == s.length() || count[s[j] - 'a'] < k) {
                        if (j > start) {
                            maxLen = max(maxLen, divide(s.substr(start, j - start), k));
                        }
                        start = j + 1;
                    }
                }
                return maxLen;
            }
        }
        
        // 所有字符都满足条件
        return s.length();
    }
};

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        def divide(s):
            if len(s) < k:
                return 0
            
            # 统计字符频次
            count = {}
            for c in s:
                count[c] = count.get(c, 0) + 1
            
            # 找到第一个不满足条件的字符
            for i, c in enumerate(s):
                if count[c] < k:
                    # 以不满足条件的字符为分割点
                    max_len = 0
                    start = 0
                    for j in range(len(s) + 1):
                        if j == len(s) or count[s[j]] < k:
                            if j > start:
                                max_len = max(max_len, divide(s[start:j]))
                            start = j + 1
                    return max_len
            
            # 所有字符都满足条件
            return len(s)
        
        return divide(s)

public class Solution {
    public int LongestSubstring(string s, int k) {
        return Divide(s, k);
    }
    
    private int Divide(string s, int k) {
        if (s.Length < k) return 0;
        
        // 统计字符频次
        int[] count = new int[26];
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        // 找到第一个不满足条件的字符
        for (int i = 0; i < s.Length; i++) {
            if (count[s[i] - 'a'] < k) {
                int maxLen = 0;
                int start = 0;
                // 以不满足条件的字符为分割点
                for (int j = 0; j <= s.Length; j++) {
                    if (j == s.Length || count[s[j] - 'a'] < k) {
                        if (j > start) {
                            maxLen = Math.Max(maxLen, Divide(s.Substring(start, j - start), k));
                        }
                        start = j + 1;
                    }
                }
                return maxLen;
            }
        }
        
        // 所有字符都满足条件
        return s.Length;
    }
}

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var longestSubstring = function(s, k) {
    if (s.length < k) return 0;
    
    const freq = {};
    for (let char of s) {
        freq[char] = (freq[char] || 0) + 1;
    }
    
    for (let char of s) {
        if (freq[char] < k) {
            let maxLen = 0;
            for (let substring of s.split(char)) {
                maxLen = Math.max(maxLen, longestSubstring(substring, k));
            }
            return maxLen;
        }
    }
    
    return s.length;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
分治法O(N × 字符集大小)O(字符集大小 + 递归深度)
滑动窗口O(N × 字符集大小)O(字符集大小)

其中 N 为字符串长度，字符集大小为 26（小写英文字母）。分治法在最坏情况下时间复杂度为 O(N²)，但平均情况下由于有效剪枝表现更好。

相关题目