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

## 思路和代码

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

public int longestSubstring(String s, int k, int left, int right) {
if(left > right) {
return 0;
}

int[] count = new int[26];
for(int i = left ; i<=right ; i++) {
count[s.charAt(i) - 'a']++;
}
int result = right - left + 1;
for(int i = left ; i<=right ; i++) {
if(count[s.charAt(i)-'a'] < k && count[s.charAt(i)-'a'] > 0) {
int leftLongest = longestSubstring(s, k, left, i-1);
int rightLongest = longestSubstring(s, k, i+1, right);
result = Math.max(leftLongest, rightLongest);

break;
}
}
return result;
}```

0 条评论

• ### leetcode363. Max Sum of Rectangle No Larger Than K

现有一个由整数构成的矩阵，问从中找到一个子矩阵，要求该子矩阵中各个元素的和为不超过k的最大值，问子矩阵中元素的和为多少? 注：后面的文章中将使用[左上角顶点坐标...

• ### 547. Friend Circles

There are N students in a class. Some of them are friends, while some are not. T...

• ### leetcode502. IPO

Suppose LeetCode will start its IPO soon. In order to sell a good price of its s...

• ### P1983 车站分级

题目描述 一条单向的铁路线上，依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别，最低为 1 级。现有若干趟车次在这条线路上行驶，每一...

• ### cf1000F. One Occurrence(线段树 set)

首先把询问离线，预处理每个数的\(pre, nxt\)，同时线段树维护\(pre\)(下标是\(pre\)，值是\(i\))，同时维护一下最大值

• ### Hebuter Daily Training 201810

有三个人Y,W,D.每个人都很想去一个地方.但是不好请假.所以能去一个 地方就很好了.Y想出来一个方法.每个人掷骰子.点数最多的赢.就可以去 他想去的地方.Y,...

• ### Lake Counting （POJ No.2386）

题意：有一个M*N的圈子，雨后有积水，然后八个方位相联通的被认为是连接在一起的。请求出圈子里共有多少个水洼。

• ### POJ-1088 滑雪 （记忆化搜索，dp）

滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 ...

• ### P2419 [USACO08JAN]牛大赛Cow Contest

题目背景 [Usaco2008 Jan] 题目描述 N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are ...