395. Longest Substring with At Least K Repeating Characters

  • 35.5%

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

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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.

方法一:

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int longestSubstring(string s, int k) {
if(s.empty() || k>s.size())
return 0;
if(k==0)
return s.size();
vector<int> cnts(26, 0);
for(auto c:s)
cnts[c-'a']++;
int idx = 0;
// 主要是char时,-'a'才是index
// cnts[s[idx]-'a'],而不是cnts[s[idx]]
while(idx<s.size() && cnts[s[idx]-'a']>=k)
idx++;
if(idx==s.size())
return s.size();
int left = longestSubstring(s.substr(0, idx), k);
int right = longestSubstring(s.substr(idx+1), k);
return max(left, right);
}
};

16ms, 23.77%, October 17, 2016

https://discuss.leetcode.com/topic/57735/c-recursive-solution

C++ recursive solution

  1. in the first pass I record counts of every character in a hashmap
  2. in the second pass I locate the first character that appear less than k times in the string. this character is definitely not included in the result, and that separates the string into two parts.
  3. keep doing this recursively and the maximum of the left/right part is the answer.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int longestSubstring(string s, int k) {
if(s.size()==0 || s.size() < k) return 0;
if(k == 0) return s.size();

unordered_map<char, int> Map;
for(int i=0; i<s.size(); i++)
Map[s[i]]++;

int idx=0;
while(idx<s.size() && Map[s[idx]] >= k) idx++;
if(idx==s.size()) return s.size();

int left = longestSubstring(s.substr(0, idx), k);
int right = longestSubstring(s.substr(idx+1), k);

return max(left, right);
}
};

https://discuss.leetcode.com/topic/57134/two-short-c-solutions-3ms-and-6ms

Two short C++ solutions (3ms and 6ms)

Sol1: a simple improvement on the naive quaratic solution. The idea is that if a locally longest substr is found, there’s no need to check substrs overlapping it.
Sol1 can run O(n) times in some cases, but worst case is O(n2). Anyway the C++ run time is 3ms.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int longestSubstring(string s, int k) {
int max_len = 0;
for (int first = 0; first+k <= s.size();) {
int count[26] = {0};
int mask = 0;
int max_last = first;
for (int last = first; last < s.size(); ++last) {
int i = s[last] - 'a';
count[i]++;
if (count[i]<k) mask |= (1 << i);
else mask &= (~(1 << i));

if (mask == 0) {
max_len = max(max_len, last-first+1);
max_last = last;
}
}
first = max_last + 1;
}
return max_len;
}

Sol2: recursive: split the string into substrs by characters of occurrence less than k. Then recursively apply the problem to each substr.
Worst case of Sol2 is O(n), because there are at most 26 levels of recursions. The C++ impl. runs 6ms. I suspect this is because the current test cases does not cover enough cases in favor of this solution in run time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int longestSubstring(string s, int k) {
return longestSubstring_recur(s, k, 0, s.size());
}

int longestSubstring_recur(const string& s, int k, int first, int last) {
int count[26] = {0};
for (int j = first; j < last; ++j) ++count[s[j] - 'a'];

int max_len = 0;
for (int j = first; j < last;) {
while (j < last && count[s[j]-'a']<k) ++j;
if (j == last) break;
int l = j;
while (l < last && count[s[l]-'a']>=k) ++l;
//all chars appear more than k times
if (j == first && l == last) return last-first;
max_len = max(max_len, longestSubstring_recur(s, k, j, l));
j = l;
}
return max_len;
}

方法二:

比较直接,但是超时

我的代码实现:

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
class Solution {
public:
int longestSubstring(string s, int k) {
if(s.empty() || k>s.size()) return 0;
if(k==0) return s.size();
int n = s.size();
vector<vector<int>>v(n+1, vector<int>(26, 0));
for(int i=0; i<n; i++){
for(int j=0; j<26; j++)
v[i+1][j] = v[i][j];
v[i+1][s[i]-'a'] = v[i][s[i]-'a']+1;
}
for(int len=n; len>0; len--){
for(int i=0; i+len<=n; i++){
bool flag = true;
for(int j=0; j<26; j++)
// 计算i+len-1行与第i行之间的差距,
// 应该从i+len-1的统计量减去i-1行的,而不是i行的
if(v[i+len][j]-v[i][j]>=1 && v[i+len][j]-v[i][j]<k){
flag = false;
break;
}
if(flag)
return len;
}
}
return 0;
}
};

python

55ms, 71.53%, October 17, 2016

https://discuss.leetcode.com/topic/57092/4-lines-python

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def longestSubstring(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
for c in set(s):
if s.count(c) < k:
return max(self.longestSubstring(t, k) for t in s.split(c))
return len(s)

49ms, 80.41%, October 17, 2016

https://discuss.leetcode.com/topic/57092/4-lines-python

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def longestSubstring(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
if len(s) < k:
return 0
c = min(set(s), key=s.count)
if s.count(c) >= k:
return len(s)
return max(self.longestSubstring(t, k) for t in s.split(c))

java

4ms, 73.89%, October 17, 2016

https://discuss.leetcode.com/topic/57372/java-3ms-divide-and-conquer-recursion-solution

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
public class Solution {
public int longestSubstring(String s, int k) {
char[] str = s.toCharArray();
return helper(str, 0, s.length(), k);
}

private int helper(char[] str, int start, int end, int k){
if(end < start) return 0;
if(end - start < k) return 0;
int[] count = new int[26];
for(int i=start; i<end; i++){
int idx = str[i] - 'a';
count[idx]++;
}

for(int i=0; i<26; i++){
if(count[i] == 0) continue;
if(count[i] < k){
for(int j=start; j<end; j++){
if(str[j] == i+'a'){
int left = helper(str, start, j, k);
int right = helper(str, j+1, end, k);
return Math.max(left, right);
}
}
}
}
return end - start;
}
}
谢谢你,可爱的朋友。