# 0395. Longest Substring with At Least K Repeating Characters

<https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters>

## 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`.

**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 <= 104`
* `s` consists of only lowercase English letters.
* `1 <= k <= 105`

## ac: divide and conquer

stuck in stackoverflow, be careful about boundary.

```java
class Solution {
    public int longestSubstring(String s, int k) {
        // edge case
        if (s == null || s.length() == 0 || k <= 0) return 0;

        return helper(s.toCharArray(), 0, s.length(), k);
    }

    private int helper(char[] chars, int l, int r, int k) {
        // exit
        if (l >= r) return 0;

        int[] cnt = new int[26];
        for (int i = l; i < r; i++) {
            cnt[chars[i] - 'a']++;  // count all characters in this substring
        }

        for (int i = l; i < r; i++) {
            if (cnt[chars[i] - 'a'] < k) {  // meet red flag
                int left = helper(chars, l, i, k);
                while (i < r - 1 && chars[i] == chars[i+1]) i++;
                int right = helper(chars, i+1, r, k);
                return Math.max(left, right);
            }
        }

        // all frequency >= k
        return r - l;
    }
}
/*
identify those whose frequency < k, as a red flag
if meet them, recursive divide into 2 parts
result will be the longer one 
if no divide, return the whole length
*/
```


---

# Agent Instructions: 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:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0395-longest-substring-with-at-least-k-repeating-characters.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
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.