Longest Substring with At Least K Repeating Characters

LeetCode 395 | Difficulty: Medium

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.

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`

Topics: Hash Table, String, Divide and Conquer, Sliding Window

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 60 ms)

Metric	Value
Runtime	60 ms
Memory	36.4 MB
Date	2022-02-09

Solution

public class Solution {
    public int LongestSubstring(string s, int k) {
        int l = 0, r = s.Length - 1;
    return KRepeatingHelper(s, k, l, r);
}

private int KRepeatingHelper(string s, int k, int l, int r)
{
    if(r<0 || l<0 || (r-l+1)<k) return 0;
    int[] counts = new int[26];
    for (int j = l; j <= r; j++)
    {
        counts[s[j] - 'a']++;
    }

    for (int i = l; i <= r; i++)
    {
        if(counts[s[i]-'a']<k)
        {
            int j = i+1;
            while(j<=r && counts[s[j]-'a']<k)
            {
                j++;
            }
            return Math.Max(KRepeatingHelper(s, k, l, i-1), KRepeatingHelper(s, k, j, r));
        }
    }
    
    return r-l+1;
}
}

---

Complexity Analysis

Approach	Time	Space
Sliding Window	$O(n)$	$O(k)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Hash map gives O(1) lookup — think about what to use as key vs value.