0395. Longest Substring with At Least K Repeating Characters

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters

Description

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

Example 1:

**Input:** s = "aaabb", k = 3
**Output:** 3
**Explanation:** The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

**Input:** s = "ababbc", k = 2
**Output:** 5
**Explanation:** The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Constraints:

• 1 <= s.length <= 104

• s consists of only lowercase English letters.

• 1 <= k <= 105

ac: divide and conquer

stuck in stackoverflow, be careful about boundary.

class Solution {
    public int longestSubstring(String s, int k) {
        // edge case
        if (s == null || s.length() == 0 || k <= 0) return 0;

        return helper(s.toCharArray(), 0, s.length(), k);
    }

    private int helper(char[] chars, int l, int r, int k) {
        // exit
        if (l >= r) return 0;

        int[] cnt = new int[26];
        for (int i = l; i < r; i++) {
            cnt[chars[i] - 'a']++;  // count all characters in this substring
        }

        for (int i = l; i < r; i++) {
            if (cnt[chars[i] - 'a'] < k) {  // meet red flag
                int left = helper(chars, l, i, k);
                while (i < r - 1 && chars[i] == chars[i+1]) i++;
                int right = helper(chars, i+1, r, k);
                return Math.max(left, right);
            }
        }

        // all frequency >= k
        return r - l;
    }
}
/*
identify those whose frequency < k, as a red flag
if meet them, recursive divide into 2 parts
result will be the longer one 
if no divide, return the whole length
*/