algoadvance

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 at least k.

Clarifying Questions

1. What is the length of the string s?
   • The length can vary but let’s consider typical lengths for competitive programming constraints, often up to 10^5 characters.
2. What kind of characters does the string s contain?
   • The string s contains only lowercase English letters.
3. Can k be greater than the length of the string s?
   • Yes, in such cases the return value should be 0 because it’s impossible to have any substring with repeating characters k times.
4. Can the input string s be empty?
   • Yes, if s is empty, the function should return 0.

Strategy

1. Divide and Conquer:
   • If any character appears fewer than k times, then it cannot be part of the substring we are looking for.
   • We can split the string at these characters and recursively find the solution in the resulting substrings.
2. Recurrence Relation:
   • The base case is if the string length is zero or if all characters in the given substring meet the requirement of appearing at least k times.
3. Helper Function:
   • Write a helper function that performs the divide and conquer strategy.

Here is the plan:

1. Implement a recursive function that:
   • Counts the frequency of characters in the substring s.
   • Splits s at characters whose frequency is less than k.
   • Recursively evaluates each partitioned substring and returns the maximum length of valid substrings.

Code

def longestSubstring(s: str, k: int) -> int:
    def helper(substring: str) -> int:
        if len(substring) == 0:
            return 0
        
        # Frequency count of characters
        freq = {}
        for char in substring:
            if char in freq:
                freq[char] += 1
            else:
                freq[char] = 1
        
        for char in freq:
            if freq[char] < k:
                # Split by this character and recursively solve
                return max(helper(part) for part in substring.split(char))
        
        # All characters meet or exceed k frequency
        return len(substring)
    
    return helper(s)

# Example usage:
s = "aaabb"
k = 3
print(longestSubstring(s, k))  # Output: 3

Time Complexity

• The time complexity is O(n * m) where n is the length of the string and m is the number of unique characters in the string. Here’s the breakdown:
  • Splitting a string on a character and checking each part takes O(n) in the worst case.
  • The recursion depth can be up to m where m is limited by the number of unique characters (at most 26 for lowercase English letters).
• In practice, this complexity is efficient for strings up to length of 10^5 given the constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?