395. Longest Substring with At Least K Repeating Characters

Link

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Solution

也是根據sliding windows的作法，先找到有可能的然後試著控制left讓它真的valid。

若不能valid，要將left復原。然後繼續right增加找找看下個可能。

class Solution {
    public int longestSubstring(String s, int k) {
        int left = 0, max = 0;
        int[] count = new int[26];;
        for(int right = 0; right < s.length(); right++){
            count[s.charAt(right) - 'a']++;
            
            if(count[s.charAt(right) - 'a'] >= k){
                while( right - left + 1 >= k){
                    if(isValid(count, k)){
                        max = Math.max(max, right - left + 1);
                        break;
                    }
                    count[s.charAt(left) - 'a']--;
                    left++;
                }
                for(int i = 0; i < left; i++){
                    count[s.charAt(i) - 'a']++;
                }
                left = 0;
            }
        }
        return max;
    }
    
    public boolean isValid(int[] count, int k){
        
        for(int i = 0; i < 26; i++){
            if(count[i] < k && count[i] != 0){
                return false;
            }
        }
        return true;
    }
    
}