# 0395. Longest Substring with At Least K Repeating Characters
###### tags: `Leetcode` `Medium` `Divide and Conquer` `Sliding Window`
Link: https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/description/
## 思路
### Divide and Conquer $O(N^2)$ $O(N)$
和[1763. Longest Nice Substring](https://hackmd.io/cIMdRw03R_iRQtFsbS7kNA)有点像
对于那些出现次数少于k的字符，是“害群之马”，它们放在任何一个子序列中都会违反题意的。所以一个直观的想法是，将那些“害群之马”作为splitor，将原序列分割成若干子序列，然后递归调用函数本身，找到最长的有效子序列。递归的边界是，如果整个序列所有的字符频次都大于等于k，就可以返回序列的长度；如果整个序列的总长度都小于k，那么就返回零
### Sliding Window $O(26N)$ $O(N)$
这道题和别的sliding window不一样的地方在于这道题是一个固定window中unique character number的滑窗
只要固定了左指针和区间不同字母的个数，那么我们就可以确定右指针最远的位置，然后查看区间内是否每个字母出现的频次都大于k
可以想见，左指针的移动，必然也会导致右指针的单向移动
## Code
### Divide and Conquer

class Solution {
    public int longestSubstring(String s, int k) {
        int[] cnt = new int[26];
        int n = s.length();
        for(int i=0; i<n; i++) cnt[s.charAt(i)-'a']++;
        int ans = 0;
        int prev = 0;
        for(int i=0; i<n; i++){
            if(cnt[s.charAt(i)-'a']<k){
                ans = Math.max(ans, longestSubstring(s.substring(prev, i), k));
                prev = i+1;
            }
        }
        if(prev==0) return n;
        else ans = Math.max(ans, longestSubstring(s.substring(prev), k));
        return ans;
    }
}

### Sliding Window

class Solution {
    public int longestSubstring(String s, int k) {
        int[] countMap = new int[26];
        int maxUnique = getMaxUnique(s);
        int ans = 0;
        for(int i=1; i<=maxUnique; i++){
            Arrays.fill(countMap, 0);
            int l = 0, r = 0, uni = 0, countAtLeastK = 0;
            while(r<s.length()){
                if(countMap[s.charAt(r)-'a']==0) uni++;
                countMap[s.charAt(r)-'a']++;
                if(countMap[s.charAt(r)-'a']==k) countAtLeastK++;
                
                while(uni>i){
                    if(countMap[s.charAt(l)-'a']==k) countAtLeastK--;
                    countMap[s.charAt(l)-'a']--;
                    if(countMap[s.charAt(l)-'a']==0) uni--;
                    l++;
                }

                if(uni==i && countAtLeastK==uni){
                    ans = Math.max(ans, r-l+1);
                }
                r++;
            }
        }
        return ans;
    }
    private int getMaxUnique(String s){
        int[] cnt = new int[26];
        int uni = 0;
        for(int i=0; i<s.length(); i++){
            if(cnt[s.charAt(i)-'a']==0) uni++;
            cnt[s.charAt(i)-'a']++;
        }
        return uni;
    }
}