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

# 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)