# 395 Longest Substring with At Least K Repeating Characters

## 395. [Longest Substring with At Least K Repeating Characters](https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/description/)

## 1. Question

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

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

## 2. Implementation

**(1)** **Two Pointers + Hash**

思路: 由于题目说了string只包含lowercase的字母，所以我们可以列举包含1个字母到包含全部26个字母情况下，找出满足条件的最长子串.其中unique代表不同的字母个数，atLeastK代表在子串中重复出现的次数至少k次的字母的个数

```java
class Solution {
    public int longestSubstring(String s, int k) {
        int[] map = new int[256];
        int start = 0, end = 0, unique = 0, atLeastK = 0;
        int maxLen = 0;

        for (int target = 1; target <= 26; target++) {
            Arrays.fill(map, 0);
            start = 0;
            end = 0;
            unique = 0;
            atLeastK = 0;

            while (end < s.length()) {
                if (map[s.charAt(end)] == 0) {
                    ++unique;
                }

                if (map[s.charAt(end)] == k - 1) {
                    ++atLeastK;
                }

                ++map[s.charAt(end)];
                ++end;

                while (unique > target) {
                    if (map[s.charAt(start)] == k) {
                        --atLeastK;
                    }

                    if (map[s.charAt(start)] ==  1) {
                        --unique;
                    }
                    --map[s.charAt(start)];
                    ++start;
                }

                // 当子串中不同字母的个数等于target，且所以这些不同的字母至少出现k次，更新maxLen
                if (unique == target && atLeastK == unique) {
                    maxLen = Math.max(maxLen, end - start);
                }
            }
        }
        return maxLen;
    }
}
```

**(2) Divide and Conquer**

```java
class Solution {
    public int longestSubstring(String s, int k) {
        return findLongestSubstring(s, k, 0, s.length() - 1);
    }

    public int findLongestSubstring(String s, int k, int start, int end) {
        if (start > end || end - start + 1 < k) {
            return 0;
        }

        int[] count = new int[26];
        for (int i = start; i <= end; i++) {
            ++count[s.charAt(i) - 'a'];
        }

        for (int i = 0; i < 26; i++) {
            if (count[i] > 0 && count[i] < k) {
                int index = s.indexOf((char)(i + 'a'), start);

                return Math.max(findLongestSubstring(s, k, start, index - 1), findLongestSubstring(s, k, index + 1, end));
            }
        }
        return end - start + 1;
    }
}
```

## 3. Time & Space Complexity

**Two Pointers + Hash:** 时间复杂度O(26 \* n), 空间复杂度O(1)

**Divide and Conquer:** 时间复杂度O(n^2), 空间复杂度O(n)


---

# 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://protegejj.gitbook.io/algorithm-practice/leetcode/two-pointers/395-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.