Longest Substring with At Least K Repeating Characters

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.

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.

Constraints:

• 1 <= s.length <= 10^4
• s consists of only lowercase English letters.
• 1 <= k <= 10^5

# Longest Substring with At Least K Repeating Characters

## Problem Description

Given a string `s` and an integer `k`, the task is to find 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, the function should return 0.

**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.

## Brute Force Solution

A naive approach would involve generating all possible substrings of the input string `s` and, for each substring, checking if the frequency of each character is at least `k`. We would then keep track of the longest substring that satisfies this condition.

```python
def longestSubstring_brute_force(s, k):
    n = len(s)
    max_len = 0
    for i in range(n):
        for j in range(i, n):
            sub = s[i:j+1]
            counts = {}
            for char in sub:
                counts[char] = counts.get(char, 0) + 1
            valid = True
            for char in counts:
                if counts[char] < k:
                    valid = False
                    break
            if valid:
                max_len = max(max_len, len(sub))
    return max_len

Optimal Solution

A more efficient solution uses a divide-and-conquer approach. The idea is to find characters in the string whose frequency is less than k. We then split the string at these characters and recursively solve the subproblems for the substrings obtained.

def longestSubstring(s, k):
    n = len(s)
    if n == 0 or k > n:
        return 0
    if k <= 1:
        return n

    counts = {}
    for char in s:
        counts[char] = counts.get(char, 0) + 1

    for i in range(n):
        if counts[s[i]] < k:
            left = longestSubstring(s[:i], k)
            right = longestSubstring(s[i+1:], k)
            return max(left, right)

    return n

Big(O) Run-time Analysis

• Brute Force: The brute force solution has a time complexity of O(n^3), where n is the length of the string s. This is because we generate all possible substrings (O(n^2)) and, for each substring, we iterate through it to count character frequencies (O(n)).
• Optimal Solution: The optimal solution has a time complexity of O(n), where n is the length of the string. At each level of recursion, we iterate through the string once to find characters that violate the frequency condition. The string is split at most n times across all recursion levels. The depth of the recursion can be at most n.

Big(O) Space Usage Analysis

• Brute Force: The brute force solution has a space complexity of O(n), where n is the length of the string s. This is due to the space used to store the substrings and the character counts.
• Optimal Solution: The optimal solution has a space complexity of O(n), where n is the length of the string s. This is due to the recursion stack, which can grow up to n in the worst case (when the string is repeatedly split into single characters). Also, we are using a dictionary that stores character frequencies that can be maximum of size O(26) which is O(1). The recursion stack dominates the space complexity giving us O(n).

Edge Cases

1. Empty String: If the input string s is empty, the function should return 0.
2. k > Length of String: If k is greater than the length of the string s, no substring can satisfy the condition, and the function should return 0.
3. k <= 1: If k is less than or equal to 1, any substring satisfies the condition, and the function should return the length of the string s.
4. String contains only 1 character repeated: For example, s = "aaaaa", k = 3. The function should correctly return 5 if k <= 5.
5. String contains all characters with frequency >= k: For example s = "aabbcc", k = 2, function should return 6.