395. Longest Substring with At Least K Repeating Characters

/**
 * Sliding Window
 *
 * Time Complexity: O(26 * N)
 *
 * Space Complexity: O(26) = O(1)
 *
 * N = Length of the input string S.
 */
class Solution {
    public int longestSubstring(String s, int k) {
        if (s == null || s.length() == 0 || s.length() < k) {
            return 0;
        }
        if (k <= 1) {
            return s.length();
        }

        int maxResult = 0;
        int[] counts = new int[26];
        int maxTarget = Math.min(26, s.length());

        for (int target = 1; target <= maxTarget; target++) {
            Arrays.fill(counts, 0);
            int start = 0;
            int end = 0;
            int uniqueChars = 0;
            int charsNoLessThanK = 0;

            while (end < s.length()) {
                int endChar = s.charAt(end) - 'a';
                if (counts[endChar] == 0) {
                    uniqueChars++;
                }
                counts[endChar]++;
                if (counts[endChar] == k) {
                    charsNoLessThanK++;
                }
                end++;

                while (uniqueChars > target) {
                    int startChar = s.charAt(start) - 'a';
                    if (counts[startChar] == k) {
                        charsNoLessThanK--;
                    }
                    counts[startChar]--;
                    if (counts[startChar] == 0) {
                        uniqueChars--;
                    }
                    start++;
                }

                // if we found a string where the number of unique chars equals our target and
                // all those chars are repeated at least K times then update max
                if (uniqueChars == target && uniqueChars == charsNoLessThanK) {
                    maxResult = Math.max(maxResult, end - start);
                }
            }
        }

        return maxResult;
    }
}