Code Implementation

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        def helper(l, r):
            if r - l < k:
                return 0
            count = {}
            for i in range(l, r):
                count[s[i]] = count.get(s[i], 0) + 1
            for mid in range(l, r):
                if count[s[mid]] < k:
                    midNext = mid + 1
                    while midNext < r and count[s[midNext]] < k:
                        midNext += 1
                    return max(helper(l, mid), helper(midNext, r))
            return r - l
        return helper(0, len(s))
    

class Solution {
public:
    int longestSubstring(string s, int k) {
        return helper(s, 0, s.size(), k);
    }
    int helper(const string& s, int l, int r, int k) {
        if (r - l < k) return 0;
        int count[26] = {0};
        for (int i = l; i < r; ++i) count[s[i] - 'a']++;
        for (int mid = l; mid < r; ++mid) {
            if (count[s[mid] - 'a'] < k) {
                int midNext = mid + 1;
                while (midNext < r && count[s[midNext] - 'a'] < k) midNext++;
                return max(helper(s, l, mid, k), helper(s, midNext, r, k));
            }
        }
        return r - l;
    }
};
    

class Solution {
    public int longestSubstring(String s, int k) {
        return helper(s, 0, s.length(), k);
    }
    private int helper(String s, int l, int r, int k) {
        if (r - l < k) return 0;
        int[] count = new int[26];
        for (int i = l; i < r; ++i) count[s.charAt(i) - 'a']++;
        for (int mid = l; mid < r; ++mid) {
            if (count[s.charAt(mid) - 'a'] < k) {
                int midNext = mid + 1;
                while (midNext < r && count[s.charAt(midNext) - 'a'] < k) midNext++;
                return Math.max(helper(s, l, mid, k), helper(s, midNext, r, k));
            }
        }
        return r - l;
    }
}
    

var longestSubstring = function(s, k) {
    function helper(l, r) {
        if (r - l < k) return 0;
        let count = {};
        for (let i = l; i < r; ++i) {
            count[s[i]] = (count[s[i]] || 0) + 1;
        }
        for (let mid = l; mid < r; ++mid) {
            if (count[s[mid]] < k) {
                let midNext = mid + 1;
                while (midNext < r && count[s[midNext]] < k) midNext++;
                return Math.max(helper(l, mid), helper(midNext, r));
            }
        }
        return r - l;
    }
    return helper(0, s.length);
};
    

Problem Description

Given a string s and an integer k, find the length of the longest substring of s such that every character in this substring appears at least k times.
The substring must be contiguous, and you may not rearrange the string. There is no guarantee that a valid substring exists.
Key constraints:

• Each character in the substring must appear at least k times.
• The substring must be contiguous within s.
• You cannot reuse characters from outside the substring.
• There may be multiple valid substrings; you must return the length of the longest one.

Thought Process

The problem asks us to find the longest contiguous substring where each character appears at least k times.
The brute-force way would be to check every possible substring, count the frequency of each character, and see if all frequencies are at least k. However, this would be very slow for large strings since there are O(n²) substrings and counting frequencies for each takes O(n) time, resulting in O(n³) time complexity.
We want to optimize. Notice that if a character in the substring appears less than k times, then any substring containing that character cannot be valid. So, if we split the string at such characters, we can recursively solve the problem on the resulting segments.
This is a classic "divide and conquer" or "recursive partitioning" approach, where we use the characters with insufficient frequency as natural split points.

Solution Approach

The optimized solution uses recursion and frequency counting. Here's how it works step-by-step:

1. Base case: If the length of the substring is less than k, it's impossible for every character to meet the requirement, so return 0.
2. Count frequencies: For the current substring, count how many times each character appears.
3. Find split points: Scan the substring. If you find a character whose total frequency in this substring is less than k, this character cannot be part of any valid substring.
4. Divide and recurse: Split the substring at this character (and any consecutive characters with insufficient frequency) and recursively solve for the left and right parts. Take the maximum result.
5. All valid: If every character in the substring appears at least k times, then the entire substring is valid, so return its length.

We use a hash map or array to count character frequencies efficiently. This approach ensures that we only examine necessary substrings and don't waste time on obviously invalid ones. The recursion naturally breaks the problem into smaller parts, and we only process each segment as needed.

Example Walkthrough

Let's walk through the example s = "ababbc", k = 2:

1. Count frequencies: {'a':2, 'b':3, 'c':1}
2. The character 'c' appears only once, which is less than k. So, any valid substring cannot include 'c'.
3. Split at 'c': We have two substrings to consider: "ababb" (before 'c') and "" (after 'c').
4. Recursively analyze "ababb":
   • Frequencies: {'a':2, 'b':3}
   • Both 'a' and 'b' appear at least 2 times. So, the entire substring "ababb" is valid. Its length is 5.
5. Analyze the "" substring (after 'c'): it's empty, so length 0.
6. The answer is max(5, 0) = 5.

Time and Space Complexity

Brute-force approach:

• There are O(n²) substrings.
• For each substring, counting frequencies takes O(n).
• Total: O(n³).

• Each recursive call splits the string at a character that cannot be part of any valid substring.
• In the worst case, if every split only reduces the size by 1, there could be O(n) levels of recursion, each doing O(n) work for frequency counting.
• But in practice, splits are often much larger, so the average time is much better.
• Time complexity: O(26 * n) = O(n), since for each recursion, we can have at most 26 splits (for each alphabet letter).
• Space complexity: O(n) for recursion stack and frequency arrays.

The optimized approach is efficient for practical input sizes and leverages the limited alphabet size.

Summary

To solve the "Longest Substring with At Least K Repeating Characters" problem, we move beyond brute force by recognizing that characters with insufficient frequency are natural split points. By recursively partitioning the string and checking only necessary substrings, we efficiently find the answer. The key insight is that any substring containing a "bad" character can't be valid, so we can safely ignore such segments. This divide-and-conquer approach is both elegant and efficient, especially for strings with a small alphabet.