Longest Substring with At Least K Repeating Characters LeetCode solution in Java

1
// Solution 1: O(n^2) brute force
2
// time O(n^2)
3
// space O(1)
4
class Solution {
5
  public int longestSubstring(String s, int k) {
6
    if (s == null || s.isEmpty() || k > s.length()) {
7
      return 0;
8
    }
9

10
    int[] map = new int[26]; // letter -> freq
11
    int n = s.length();
12
    int max = 0; // length of longest substring T so far
13
    for (int i = 0; i < n; i++) {
14
      Arrays.fill(map, 0);
15
      for (int j = i; j < n; j++) {
16
        map[s.charAt(j) - 'a']++;
17
        if (isValid(s, i, j, k, map)) {
18
          max = Math.max(max, j - i + 1);
19
        }
20
      }
21
    }
22

23
    return max;
24
  }
25

26
  // return true if each distinct character in the substring s[left..right] appear >= k times
27
  private boolean isValid(String s, int left, int right, int k, int[] map) {
28
    int numLetters = 0; // number of distinct letters
29
    int numLettersAtLeastK = 0;
30
    for (int num : map) {
31
      if (num > 0) {
32
        numLetters++;
33
      }
34

35
      if (num >= k) {
36
        numLettersAtLeastK++;
37
      }
38
    }
39

40
    return numLettersAtLeastK == numLetters;
41
  }
42
}