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.

For this kind of problem, we definitely need to count the occurrence of each characters. Now the problem is how to get the longest substring. The idea is that for each character that has lower than k occurrence, we treat it as a separator. However, the substring that contains all chars with k occurrence may not have k occurrence anymore after the split. Thus we need to recursively call the function and find the longest substring.

The bit mask here is used to track if all characters have occurrence of at least k. We set the bit the character corresponds to 1 if it has occurrence smaller than k, later if the same character appears again and the occurrence exists k, we set the bit back to 0. If in the end the mask is 0, we know all characters have at least k occurrence.

public int longestSubstring(String s, int k) {
        if (s.length() == 0 || k == 0) {
            return s.length();
        }
        int[] chars = new int[26];
        int len = s.length();
        int mask = 0;
        for (int i = 0; i < len; i++) {
            int index = s.charAt(i) - 'a';
            chars[index]++;
            if (chars[index] < k) {
                mask |= (1 << index);
            } else {
                mask &= ~(1 << index);
            }
        }
        if (mask == 0) {
            return s.length();
        }
        int last_start = 0;
        int longest = 0;
        for (int i = 0; i < len; i++) {
            if (chars[s.charAt(i) - 'a'] < k) {
                longest = Math.max(longest, longestSubstring(s.substring(last_start, i), k));
                last_start = i + 1;
            }
        }
        longest = Math.max(longest, longestSubstring(s.substring(last_start), k));
        return longest;
    }