[LeetCode 395] Longest Substring

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: recursively

1. 每一次迭代时，每个频次小于K的字母都是不符合题目要求的，所以任何包含它的substring都不符合要求。但凡遇到他，那么就求之前substring的longest substring。然后继续求解，但是需要跳过这个字符

class Solution {
    public int longestSubstring(String s, int k) {
        if (s == null || s.length () == 0)
            return 0;
        
        int[] tracker = new int[26];
        for (char ch : s.toCharArray ()) {
            tracker[ch - 'a'] ++;
        }
        
        boolean fullString = true;
        for (int i = 0; i < s.length (); i++) {
            if (tracker[s.charAt (i) - 'a'] > 0 && tracker[s.charAt (i) - 'a'] < k) {
                fullString = false;
                break;
            }
        }
        
        if (fullString) {
            return s.length ();
        }
        
        int start = 0;
        int end = 0;
        int result = 0;
        
        while (end < s.length ()) {
            if (tracker[s.charAt (end) - 'a'] < k) {
                result = Math.max (result, longestSubstring (s.substring (start, end), k));
                start = end + 1;
            }
            end ++;
        }
        
      // to handle case like: "acbbee" k = 2;
        // cannot handle "bbee" because there is no substring after that which can trigger calculate result
        result = Math.max (result, longestSubstring (s.substring (start, end), k));
        return result;
    }
}