> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/395-longest-substring-with-at-least-k-repeating-characters.md).

# 395 Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

**Example 1:**

```
Input:
s = "aaabb", k = 3

Output:
3
```

The longest substring is "aaa", as 'a' is repeated 3 times.

**Example 2:**

```
Input:
s = "ababbc", k = 2

Output:
5
```

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

**The Idea:** The general idea is to find the longest consequtive sequence of characters that have a quantity >= k, and then recursively iterate on those substrings if things don't work out. First, I mapped characters to thier frequencies. Then I found the longest sequences of characters that occur at least k times. I then perform a check on this substring explicitly to confirm that the local characters in the substring appear k times. If not, we can greedily iterate perform that same proceedure on that substring until we do find a valid substring match. This works because we always find the largest possible substring of at least k, and split on those to find the next smallest ones.

**Complexity:** ??

```cpp
unordered_map<char, int> get_freq_map(const string &s) {
    unordered_map<char, int> s_freq;
    s_freq.reserve(s.size());
    for (int i = 0; i < s.size(); i++) {
        if (s_freq.find(s[i]) == s_freq.end()) {
            s_freq.insert({ s[i], 1 });
        }
        else s_freq[s[i]]++;
    }
    return s_freq;
}


bool isSubstringAtLeastK(const string &s, int k, unordered_map<char, int> &freq_map)
{
    for (char c : s) {
        if (freq_map[c] < k) return false;
    }
    return true;
}


int longestSubstring(const string &s, int k, unordered_map<char, int> s_freq) {
    // get ordered array where chars are >= k
    vector<bool> is_valid_i(s.size());
    for (int i = 0; i < s.size(); i++) {
        is_valid_i[i] = s_freq[s[i]] >= k;
    }

    // find the longest consequtive 1's
    int start = 0;
    int max_dist = 1;
    int temp_dist = 1;
    int i = 1;
    for (; i < is_valid_i.size(); i++) {
        if (is_valid_i[i - 1] == is_valid_i[i] && 
            is_valid_i[i-1] && is_valid_i[i]) {
            temp_dist++;
        }
        else if (temp_dist > max_dist) {
            max_dist = temp_dist;
            start = i - max_dist;
            temp_dist = 1;
        }
    }
    if (temp_dist > max_dist) {
        max_dist = temp_dist;
        start = i - max_dist;
    }

    // assert that the substring is valid
    string long_cons_substr = s.substr(start, max_dist);
    if (long_cons_substr.length() < k)
        return 0;
    unordered_map<char, int> sub_freq_map = get_freq_map(long_cons_substr);
    if (isSubstringAtLeastK(long_cons_substr, k, sub_freq_map))
        return max_dist;
    else return longestSubstring(long_cons_substr, k, sub_freq_map);
}


int longestSubstring(string s, int k) {
    return longestSubstring(s, k, get_freq_map(s));
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/395-longest-substring-with-at-least-k-repeating-characters.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.