对于一个字符串中计数长度<k的字符，他必定为分界，反之，当一个字符串中没有计数<k的字符，他就一定是符合条件的子串。
递归分治
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int longestSubstring(string s, int k) {
return helper(s, 0, s.size() - 1, k);
}
private:
int helper(string& s, int lo, int hi, int k)
{
if(lo > hi)
return 0;
int memo[26]{ 0 };
for(int i = lo; i <= hi; ++i)
++memo[s[i] - 'a'];
for(int i = lo; i <= hi; ++i)
if(memo[s[i] - 'a'] < k)
return max(helper(s, lo, i - 1, k), helper(s, i + 1, hi, k));
return hi - lo + 1;
}
};
|
以上的方法调用的递归次数较多，实际上一个分割字符可以把字符串分成好多串。就可以减少递归调用的次数
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
32
33
34
35
36
37
38
| class Solution {
public:
int longestSubstring(string s, int k) {
if(k == 1)
return s.size();
return helper(s, 0, s.size() - 1, k);
}
private:
int helper(string& s, int lo, int hi, int k)
{
if(lo > hi)
return 0;
int memo[26]{ 0 };
bool split = false;
for(int i = lo; i <= hi; ++i)
++memo[s[i] - 'a'];
for(int i = lo; i <= hi; ++i)
if(memo[s[i] - 'a'] < k)
{
split = true;
break;
}
if(!split)
return hi - lo + 1;
int i = lo, start = lo;
int ret = 0;
while(i <= hi + 1)
{
if(i == hi + 1 || memo[s[i] - 'a'] < k)
{
ret = max(ret, helper(s, start, i - 1, k));
start = i + 1;
}
++i;
}
return ret;
}
};
|
滑动窗口
对于每种子串的字符数进行枚举，如果当前字符数大于这个值，就移动左边界
维护一个less变量表示当前子串中还有几个个数未达到k。
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
32
33
34
35
36
37
38
39
40
41
| class Solution {
public:
int longestSubstring(string s, int k) {
int n = s.size();
if(k == 1)
return n;
int ret = 0;
for(int i = 1; i <= 26; ++i)
{
int memo[26]{ 0 };
int total = 0;
int less = 0;
int begin = 0, end = 0;
while(end < n)
{
if(++memo[s[end] - 'a'] == 1)
{
++total;
++less;
}
if(memo[s[end] - 'a'] == k)
--less;
while(total > i)
{
if(--memo[s[begin] - 'a'] == 0)
{
--total;
--less;
}
if(memo[s[begin] - 'a'] == k - 1)
++less;
++begin;
}
if(less == 0)
ret = max(ret, end - begin + 1);
++end;
}
}
return ret;
}
};
|