p395

发表于 | 分类于 |

LeetCode p395 Longest Substring with At Least K Repeating Characters 题解

1.题目：

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.

题意：

给你一个字符串和一个数字k,求这个字符串的最大子串，要求这个子串中每一种字符出现的字数都大于k。

2.解题思路:

先将这个字符串中所有出现次数小于k，但是大于0(注意判断大于0，即是否出现过)的字符，作为分隔点，再判断被分隔开来的子串。
直到子串中没有分隔点，返回子串长度。最后取大得到最大子串。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
public class Solution {
   
    public int longestSubstring(String s, int k) {
        if (k > s.length())  //开始没加这个判断超时了TUT
			return 0;
		
		boolean flag = true;
		char[] str = s.toCharArray();
		int[] list = new int[26 + 2];
		for (int i = 0; i < str.length; i++) {
			list[str[i] - 'a']++;
		}
		
		for (int i = 0; i < list.length; i++) {
			if (list[i] < k && list[i] > 0)
				flag = false;
		}

		if (flag)
			return str.length;
		for (int i = 0; i < str.length; i++) {
			if (list[str[i] - 'a'] < k && list[str[i] - 'a'] > 0) {
				return Math.max(longestSubstring(s.substring(0, i), k),
						longestSubstring(s.substring(i + 1, str.length), k));
			}
		}

		return str.length;
    }
}

4.一些总结：