LeetCode_ Sliding window_ Medium_ 395. Longest substring with at least k repeated characters

1. subject

Give you a string s And an integer k , Please find out s Longest substring in , The number of occurrences of each character in the substring shall not be less than k . Returns the length of this substring .

Example 1：
Input ：s = “aaabb”, k = 3
Output ：3
explain ： The longest string is “aaa” , among ‘a’ repeated 3 Time .

Example 2：
Input ：s = “ababbc”, k = 2
Output ：5
explain ： The longest string is “ababb” , among ‘a’ repeated 2 Time , ‘b’ repeated 3 Time .

Tips ：
1 <= s.length <= 10⁴
s It's only made up of lowercase letters
1 <= k <= 10⁵

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters

2. Ideas

（1） The law of violent exhaustion
This method is easy to think of , Namely Traversal string s All lengths of are greater than or equal to k The string of , Judge the number of occurrences of each character in them , And use res Record the length of the longest substring that meets the conditions , After traversal, return res that will do , In the judgment process, you can use a hash table to store the number of occurrences of each string . But the time complexity of this method is high , stay LeetCode Submit on will appear “ Time limit exceeded ” A hint of .

（2） The sliding window
Train of thought reference Official solution to this problem .

3. Code implementation （Java）

// Ideas 1———— The law of violent exhaustion 
class Solution {
    
    public int longestSubstring(String s, int k) {
    
        // key / value : character / Corresponding number of occurrences 
        HashMap<Character, Integer> hashMap = new HashMap<>();
        int length = s.length();
        int res = 0;
        for (int i = 0; i < length; i++) {
    
            for (int j = i + k; j <= length; j++) {
    
                // Get substring 
                String subStr = s.substring(i, j);
                boolean flag = true;
                hashMap.clear();
                for (int l = 0; l < subStr.length(); l++) {
    
                    char c = subStr.charAt(l);
                    hashMap.put(c, hashMap.getOrDefault(c, 0) + 1);
                }
                for (int cnt : hashMap.values()) {
    
                    if (cnt < k) {
     
                        flag = false;
                        break;
                    }
                }
                if (flag == true) {
    
                    res = Math.max(res, subStr.length());
                }
            }
        }
        return res;
    }
}

// Ideas 2———— The sliding window 
class Solution {
    
    public static int longestSubstring(String s, int k) {
    
        int res = 0;
        int length = s.length();
        for (int i = 1; i <= 26; i++) {
    
            int left = 0;
            int right = 0;
            int[] cnt = new int[26];
            int total = 0;
            int less = 0;
            while (right < length) {
    
                cnt[s.charAt(right) - 'a']++;
                if (cnt[s.charAt(right) - 'a'] == 1) {
    
                    total++;
                    less++;
                }
                if (cnt[s.charAt(right) - 'a'] == k) {
    
                    less--;
                }
                while (total > i) {
    
                    cnt[s.charAt(left) - 'a']--;
                    if (cnt[s.charAt(left) - 'a'] == k - 1) {
    
                        less++;
                    }
                    if (cnt[s.charAt(left) - 'a'] == 0) {
    
                        total--;
                        less--;
                    }
                    left++;
                }
                if (less == 0) {
    
                    res = Math.max(res , right - left + 1);
                }
                right++;
            }
        }
        return res;
    }
}