395. Longest Substring with At Least K Repeating Characters – Leetcode Solutions

Example 1:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input: s = "ababbc", k = 2
Output: 5
Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        # Helper function to determine the length of the longest valid substring
        def helper(s: str, k: int) -> int:
            # Base case: If the string length is less than k, return 0
            if len(s) < k:
                return 0
            
            # Count the frequency of each character in the string
            freq = {}
            for char in s:
                freq[char] = freq.get(char, 0) + 1
            
            # Identify characters that appear fewer than k times
            for char, count in freq.items():
                if count < k:
                    # Split the string around this character and recursively check the parts
                    return max(helper(substring, k) for substring in s.split(char))
            
            # If all characters occur at least k times, the entire string is valid
            return len(s)
        
        # Call the helper function with the input string
        return helper(s, k)

class Solution {
public:
    int longestSubstring(std::string s, int k) {
        // Helper function for divide and conquer
        return helper(s, 0, s.size(), k);
    }

private:
    // Divide and conquer method to find the longest valid substring
    int helper(const std::string& s, int start, int end, int k) {
        // Base case: If the substring length is less than k, return 0
        if (end - start < k) {
            return 0;
        }

        // Frequency map to count the occurrences of each character in the substring
        std::unordered_map<char, int> freq;
        for (int i = start; i < end; ++i) {
            ++freq[s[i]];
        }

        // Check for characters with a frequency less than k
        for (int i = start; i < end; ++i) {
            if (freq[s[i]] < k) {
                // If a character has a frequency less than k, split the string at this character
                int left = helper(s, start, i, k);    // Recur for the left part
                int right = helper(s, i + 1, end, k); // Recur for the right part
                return std::max(left, right);
            }
        }

        // If all characters in the substring have a frequency >= k, return its length
        return end - start;
    }
};

var longestSubstring = function(s, k) {
    // Helper function to check the longest substring with a specific number of unique characters
    const longestSubstringWithNUniqueChars = (s, k, uniqueTarget) => {
        let start = 0, end = 0, maxLen = 0;
        let charFrequency = {}; // Tracks frequency of characters in the current window
        let uniqueCount = 0; // Number of unique characters in the current window
        let charsWithEnoughFrequency = 0; // Number of characters in the window with frequency >= k
        
        while (end < s.length) {
            // Expand the window by including s[end]
            const charEnd = s[end];
            if (!charFrequency[charEnd]) {
                charFrequency[charEnd] = 0;
                uniqueCount++;
            }
            charFrequency[charEnd]++;
            if (charFrequency[charEnd] === k) {
                charsWithEnoughFrequency++;
            }
            end++;
            
            // Shrink the window until uniqueCount <= uniqueTarget
            while (uniqueCount > uniqueTarget) {
                const charStart = s[start];
                if (charFrequency[charStart] === k) {
                    charsWithEnoughFrequency--;
                }
                charFrequency[charStart]--;
                if (charFrequency[charStart] === 0) {
                    uniqueCount--;
                    delete charFrequency[charStart];
                }
                start++;
            }
            
            // Update the maximum length if all unique characters in the window have frequency >= k
            if (uniqueCount === uniqueTarget && uniqueCount === charsWithEnoughFrequency) {
                maxLen = Math.max(maxLen, end - start);
            }
        }
        
        return maxLen;
    };
    
    let maxLen = 0;
    const uniqueCharCount = new Set(s).size; // Total unique characters in the string
    
    // Try for every possible number of unique characters in the substring
    for (let currentUnique = 1; currentUnique <= uniqueCharCount; currentUnique++) {
        maxLen = Math.max(maxLen, longestSubstringWithNUniqueChars(s, k, currentUnique));
    }
    
    return maxLen;
};

class Solution {
    public int longestSubstring(String s, int k) {
        // Helper function that uses divide and conquer
        return longestSubstringHelper(s, 0, s.length(), k);
    }
    
    // Function to find the longest substring in a given range [start, end)
    private int longestSubstringHelper(String s, int start, int end, int k) {
        // Base case: if the length of the substring is less than k, return 0
        if (end - start < k) return 0;
        
        // Step 1: Count the frequency of each character in the current substring
        int[] freq = new int[26]; // 26 for each lowercase letter
        for (int i = start; i < end; i++) {
            freq[s.charAt(i) - 'a']++;
        }
        
        // Step 2: Iterate over the substring and find characters that don't meet the frequency requirement
        for (int i = start; i < end; i++) {
            if (freq[s.charAt(i) - 'a'] < k) {
                // This character doesn't appear at least k times
                // Use this character as a split point
                int left = longestSubstringHelper(s, start, i, k);
                int right = longestSubstringHelper(s, i + 1, end, k);
                // Return the maximum length found in the left and right partitions
                return Math.max(left, right);
            }
        }
        
        // Step 3: If all characters in the current range meet the condition, return the length of the substring
        return end - start;
    }
}