Problem

Longest Substring with At Least K Repeating Characters

Intuition

  1. The problem is to get the longest such substring that every character must appear no less than K times.
  2. My first method is to check all the substring of the string. No doubt that it’s TLE.
  3. After discussion, I use Divide & Conqure to solve it.
  4. As for the string S, find all characters that appears less than K times. Then we can divide S into many substring and check new string S. Lastly, we can get the answer.

Code

class Solution {
    int ans;
    private void checkRange(int s, int e, int k, String str){
        if(e - s + 1 < k || e - s + 1 < ans){
            return ;
        }
        List<Integer> obs = new ArrayList<>();
        obs.add(-1);
        Map<Integer, List<Integer>> mp = new HashMap<>();
        for(int i = s; i <= e; i ++){
            int cur = str.charAt(i) - 'a';
            if(mp.containsKey(cur)){
                List<Integer> temp = mp.get(cur);
                temp.add(i);
            } else {
                List<Integer> temp = new ArrayList<>();
                temp.add(i);
                mp.put(cur, temp);
            }
        }
        for(int key : mp.keySet()){
            if(mp.get(key).size() < k){
                obs.addAll(mp.get(key));
            }
        }
        obs.add(e + 1);
        if(obs.size() == 2){
            ans = Math.max(ans, e - s + 1);
        } else {
            for(int i = 0; i < obs.size() - 1; i ++){
                checkRange(obs.get(i) + 1, obs.get(i + 1) - 1, k, str);
            }
        }
    }
    public int longestSubstring(String s, int k) {
        ans = 0;
        checkRange(0, s.length() - 1, k, s);
        return ans;
    }
}