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.

My answer

I didn't figure out the answer. Answer below is based on top of one good answer. Basically this is a good example of Divide and Conquer. We need to find out which substring is worth checking, and skip ineligible substring, divide substring by such `eligibility`, and conquer each one.

I think one key condition of using Divide and Conquer is if this problem can be divided into sub-problem, and the answer to same question when applied to the sub-problem can help for original problem.

class Solution {
    public int longestSubstring(String s, int k) {
        int defaultLength = 0;
        if (s == null || s.length() < k) {
            return defaultLength;
        }
        Map<Character, Integer> charLocations = new HashMap<Character,Integer>();
        
        for (int i = 0; i < s.length(); i ++) {
            Integer count = charLocations.getOrDefault(s.charAt(i), 0);
            count++;
            charLocations.put(s.charAt(i), count);
        }

        for (int i = 0; i < s.length(); i ++) {
            if (charLocations.get(s.charAt(i)) >= k) {
                int j = i + 1;
                while (j < s.length() && charLocations.get(s.charAt(j)) >= k) {
                    j ++;
                }
                if (j == s.length()) {
                    return j - i;
                }
                 return Math.max(longestSubstring(s.substring(i, j), k), longestSubstring(s.substring(j), k));
            }
        }
        
        return defaultLength;
    }
}