LeetCode 395. 至少有K个重复字符的最长子串

我会带着你远行 2022-10-27 06:21 70阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
[题解][Link 1]

//循环26次，每次次限定符合条件的不同字符有1，2，3.....26个
    class Solution {
        
        public int longestSubstring(String s, int k) {
        
            int res = 0;
    
            for(int i = 1; i <= 26; i++){
        
                res = Math.max(res, helper(s, k, i));
            }
            return res;
        }
        private int helper(String s, int k, int i){
        
            int[] map = new int[26];
            int l = 0;
            int r = 0;
            int res = Integer.MIN_VALUE;
            int cnt = 0;
            int numNoLessThanK = 0;
            while(r < s.length()){
        
                int cl = s.charAt(r) - 'a';
                if(map[cl]++ == 0){
        
                    cnt++;
                }
                if(map[cl] == k){
        
                    numNoLessThanK++;
                }
                r++;
                while(cnt > i){
        
                    int c2 = s.charAt(l) - 'a';
                    if(map[c2]-- == k){
        
                        numNoLessThanK--;
                    }
                    if(map[c2] == 0){
        
                        cnt--;
                    }
                    l++;
                }
                if(cnt == numNoLessThanK){
        
                    res = Math.max(res, r - l);
                }
            }
            return res;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/cff41c21f23f478aa137efdd2740a9c6.png
[Link 1]: https://leetcode-cn.com/problems/minimum-window-substring/solution/labuladongde-suan-fa-xiao-chao-javaban-b-glhm/