Longest Substring with at least K repeating Characters

395.Longest Substring with At Least K Repeating Characters

String

Sliding Window

Hash Table

Problem Statement:

Given a string s and an integer k, return the length of the longest substring such that the frequency of each character in this substring is greater than or equal to k. (There is a divide and conquer solution but slidng window is superior.)

Example:

Input:

s = "aaabb", k = 3

→

Output:

3

Java Solution:

public int longestSubstring(String s, int k) {
    // Edge case: if string is null or length is less than k, return 0
    if (s == null || s.length() == 0 || k > s.length()) return 0;

    int maxUnique = getMaxUniqueCharacters(s);  // Get max unique chars in string
    int maxLength = 0;

    // Try all possible numbers of unique characters
    for (int currentUnique = 1; currentUnique <= maxUnique; currentUnique++) {
        // Sliding window variables
        int left = 0, right = 0;
        HashMap<Character, Integer> charCountMap = new HashMap<>();
        int uniqueCount = 0;  // Number of unique chars in window
        int kCount = 0;      // Number of chars appearing at least k times

        // Expand the sliding window
        while (right < s.length()) {
            char rightChar = s.charAt(right);
            charCountMap.put(rightChar, charCountMap.getOrDefault(rightChar, 0) + 1);

            if (charCountMap.get(rightChar) == 1) uniqueCount++;
            if (charCountMap.get(rightChar) == k) kCount++;

            // Shrink window if too many unique characters
            while (uniqueCount > currentUnique) {
                char leftChar = s.charAt(left);
                if (charCountMap.get(leftChar) == k) kCount--;
                charCountMap.put(leftChar, charCountMap.get(leftChar) - 1);
                if (charCountMap.get(leftChar) == 0) uniqueCount--;
                left++;
            }

            // Update max length if window is valid
            if (uniqueCount == kCount) {
                maxLength = Math.max(maxLength, right - left + 1);
            }
            right++;
        }
    }
    return maxLength;
}

// Helper function to get count of unique characters
private int getMaxUniqueCharacters(String s) {
    boolean[] seen = new boolean[26];
    int uniqueCount = 0;
    
    for (char c : s.toCharArray()) {
        if (!seen[c - 'a']) {
            uniqueCount++;
            seen[c - 'a'] = true;
        }
    }
    return uniqueCount;
}

Algorithm:

1. Try each possible count of unique characters
2. Use sliding window for each count
3. Track unique characters and k-frequency characters
4. Update max length when window is valid

Complexity:

Time: O(maxUnique * N) where maxUnique is at most 26
Space: O(1) since character count is bounded