LeetCode 395. Longest Substring with At Least K Repeating Characters

原题链接在这里：https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

题目：

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.

题解：

To make sure every char in substring appears no less than k time, we need to make sure unique count == no less than k count.

We could add one more argument uniTargetCnt, that is the target of count of unique char.

First move the runner. 

While unique count > target, move the walker.

Update the longest with target unique count.

target unique count could be [1, 26].

Time Complexity: O(n). n = s.length().

Space: O(1).

AC Java:

class Solution {
    public int longestSubstring(String s, int k) {
        if(s == null || s.length() == 0 || k <= 0){
            return 0;
        }
        
        int res = 0;
        for(int i = 1; i <= 26; i++){
            res = Math.max(res, longestTargetSubstring(s, k, i));
        }
        
        return res;
    }
    
    private int longestTargetSubstring(String s, int k, int uniTargetCnt){
        int walker = 0;
        int runner = 0;
        int [] map = new int[26];
        int uniCnt = 0;
        int overKCnt = 0;
        int res = 0;
        
        while(runner < s.length()){
            if(map[s.charAt(runner) - ‘a‘]++ == 0){
                uniCnt++;
            }
            
            if(map[s.charAt(runner++) - ‘a‘] == k){
                overKCnt++;
            }
            
            while(uniCnt > uniTargetCnt){
                if(map[s.charAt(walker) - ‘a‘]-- == k){
                    overKCnt--;
                }
                
                if(map[s.charAt(walker++) - ‘a‘] == 0){
                    uniCnt--;
                }
            }
            
            if(uniCnt == uniTargetCnt && uniCnt == overKCnt){
                res = Math.max(res, runner - walker);
            }
        }
        
        return res;
    }
}

类似Minimum Window Substring.