题解 | #至少有 K 个重复字符的最长子串# [P1-T2]

分治 递归

每次递归：
统计每个字符的出现次数 存入freq[]
遍历每一个字符，遇到freq < k的就把字符串拆分成左右两边分别求解，取max
比如 aaabbbcdddefff
对于c拆分 -> aaabbb, dddefff
aaabbb会直接return 6，
dddefff继续对e拆分 -> ddd, fff
...
...

import java.util.*;

public class Solution {
  public int longestSubstring (String s, int k) {
    return lss(s, k);
  }

  int lss(String s, int k) {
    if (s.length() == 0 || s.length() < k) return 0;
    
    int[] freq = new int[26];
    for (int i = 0; i < s.length(); i++) {
      freq[s.charAt(i) -'a']++;
    }
    
    for (int i = 0; i < s.length(); i++) {
      if (freq[s.charAt(i) -'a'] < k) {
        return Math.max(
          lss(s.substring(0, i), k),
          lss(s.substring(i+1, s.length()), k));
      } 
    }
    
    return s.length();
  }
}