🧐395 longest substring with at least k repeating characters

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

class Solution {
    public int longestSubstring(String s, int k) {
        char[] input = s.toCharArray();
        int n = input.length;
        int ans = 0;
        for (int unique = 1; unique <= 26; unique++) {
            int[] cnt = new int[26];
            int uniqueCnt = 0;
            int charLessThanK = 0;
            
            int l = 0;
            for (int r = 0; r < n; r++) {
                cnt[input[r] - 'a']++;
                //不能用>k
                if (cnt[input[r] - 'a'] == k) {
                    charLessThanK--;
                }
                // should not use else in case k is 1 (charLessThank should first -- then ++)
                if (cnt[input[r] - 'a'] == 1) {
                    uniqueCnt++;
                    //注意charLessThanK也得++
                    charLessThanK++;
                }
                while (uniqueCnt > unique) {
                    cnt[input[l] - 'a']--;
                    // 不能用<k
                    if (cnt[input[l] - 'a'] == k - 1) {
                        charLessThanK++;
                    }
                    if (cnt[input[l] - 'a'] == 0) {
                        charLessThanK--;
                        uniqueCnt--;
                    }
                    l++;
                }
                if (charLessThanK == 0) {
                    ans = Math.max(ans, r - l + 1);
                }
            }
        }
        return ans;
    }
}

难点在于想到收缩窗口的条件，直接从题出发是想不到的，因为这里收缩窗口只会破坏题要求的条件，毕竟收缩窗口时字符数量只会减少，在这里相当于是遍历了string26次，每次都用sliding window作为一个框架，条件是sliding window里unique characters的数量保证不变，这样通过控制每次循环中range里不同字母数量的不同，我们就能在26次循环中conver掉所有可能的range。用这个条件在O(n)复杂度下遍历了所有的substring，同时统计了窗口中出现频率少于k的字符数量(charLessThanK)，注意这个手法，避免了用subarray里的max count来判断(非常不好维护)。因此这里的sliding window其实只是一个载体，我觉得还可以用来解决其他题目

还有就是，char的frequency map用int array好多了啊

其实维护charGTEk更简单：

class Solution {
    public int longestSubstring(String s, int k) {
        char[] arr = s.toCharArray();
        int ans = 0;
        for (int unique = 1; unique <= 26; unique++) {
            int[] counts = new int[26];
            int uniqCnt = 0;
            int charMoreThanK = 0;
            int j = 0;
           for (int i = 0; i < arr.length; i++) {
            char ch = arr[i];
            counts[ch-'a']++;
            if (counts[ch-'a'] == 1) {
                uniqCnt++;
            }
            if (counts[ch-'a'] == k) {
                charMoreThanK++;
            }
            while (j <= i && uniqCnt > unique) {
                counts[arr[j] - 'a']--;
                if (counts[arr[j] - 'a'] == 0) {
                    uniqCnt--;
                }
                if (counts[arr[j] - 'a'] == k-1) {
                    charMoreThanK--;
                }
                j++;
            }
            if (charMoreThanK == unique) {
                ans = Math.max(ans, i-j+1);
            }
           }
        }
        return ans;
    }
}

每个字符都多于k，可以通过最少的一个都多于k，也可以从定义出发，多于k的数字符的个数等于当前所有字符的种类数，从这里就很容易想到要通过unique cnt来作为window条件了