We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Substring with At Least K Repeating Characters

Difficulty: Medium

Problem Description

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k. If no such substring exists, return 0.

Key Insights

  • The problem requires finding a substring where all characters appear at least k times.
  • A sliding window or divide-and-conquer approach can be effective to explore substrings efficiently.
  • The use of a hash table (or dictionary) can help in counting the frequency of characters in the substring.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case for the divide-and-conquer approach, but can be optimized with the sliding window technique to O(n). Space Complexity: O(1) for the frequency count since the character set is limited to lowercase English letters.

Solution

To solve the problem, we can use a sliding window approach. The idea is to maintain a window of characters and expand it until we find a character that appears less than k times. When this happens, we can shrink the window from the left. We also keep track of the maximum length of valid substrings found during this process. We will use a hash table to count the frequency of characters within the current window.

Code Solutions

def longestSubstring(s: str, k: int) -> int:
    # Helper function to determine if a substring is valid
    def is_valid(count_map, k):
        for count in count_map.values():
            if count < k:
                return False
        return True
    
    max_length = 0
    for unique_chars in range(1, 27):  # There are 26 lowercase letters
        count_map = {}
        left = 0
        right = 0
        current_unique = 0
        
        while right < len(s):
            # Add character at right to the window
            if count_map.get(s[right], 0) == 0:
                current_unique += 1
            count_map[s[right]] = count_map.get(s[right], 0) + 1
            
            # Shrink the window if we have more unique characters than allowed
            while current_unique > unique_chars:
                count_map[s[left]] -= 1
                if count_map[s[left]] == 0:
                    current_unique -= 1
                left += 1
            
            # Check if current window is valid and update max_length
            if is_valid(count_map, k):
                max_length = max(max_length, right - left + 1)
            
            right += 1
            
    return max_length
← Back to All Questions