Code & Func

打卡，第12天

今天刷的题目是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.

Input: s = “aaabb”, k = 3

Output: 3

The longest substring is “aaa”, as ‘a’ is repeated 3 times.

Input: s = “ababbc”, k = 2

Output: 5

The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.

本来是以为像Longest Substring Without Repeating Characters一样用两个下标去遍历，然后动态规划的去做（问题来了？动态规划是什么。。。我竟然还没有去翻，拖延症又犯了），一开始发现我可能需要在遍历前先知道当前字符是否会出现k次啊，恩，那就先用一个unordered_map去遍历一遍字符串来记录出现的次数吧：

1
unordered_map<char,int> count;
2
for(auto c:s)
3
    ++count[c];

然后就开始思考什么时候i应该向前移动了，当s[j]出现的次数小于k时,i就应该变成j+1了，恩，这个时候我就应该计算s[i,j]的长度,显然不能直接是j-i来算长度啦，因为在以下情况时，它就失灵了：

Input: s = “ababacb” k = 3

如果直接j-i的话，就会得出5，但是显然在这个子串中，b只出现了两次，所以我们还要回去检查一遍，然后就开始想要怎么计算长度，大概需要一个下标t从i一直往j移动，遍移动遍计算，那么问题来了，我怎么知道什么时候t应该往前走，什么时候应该计算，恩，干脆先遍历一遍计算一下出现次数，然后我才能知道什么计算。。。突然发现有点不对，我好像写的代码是重复的，恩，按照这个逻辑一直走下去，好像我会一直递归这个过程，想了想就写成递归的形式吧，看起来好像就莫名其妙的写出了一个用分治法的解法了：

先遍历一遍计算整个串中出现的次数
然后开始从头遍历，找出一个t使得count[ s[t] ] < k
找到了，我们就分别计算s[i:t]和s[t+1:j]的最大长度即可
没找到，那么说明整个串是符合的，我们直接返回串长度即可
递归结束的条件就是当串长度比k小的时候啦。

1
string s;   //为了减少递归传递而设置的全局变量
2
int t;
3

4
int longestSubstring(string ss, int tt) {
5
    if (tt <= 1) return ss.size();
6
    s = ss;
7
    t = tt;
8
    unordered_map<char,int> count;
9
    for(auto c:s)
10
        ++count[c];
11
    return longestSubString(0,s.size(),count);
12
}
13

14
int longestSubString(int beg,int end,unordered_map<char,int> &imap ){
15
    if (end - beg < t) return 0;
12 collapsed lines
16
    int j;
17
    for(j = beg;j < end && imap[s[j]] >= t;j++)
18
        /*do nothing*/;
19
    if (j == end) return end - beg;
20
    unordered_map<char,int> right;
21
    for(int k = beg;k < j;k++){
22
        --imap[ s[k] ];//重复利用imap，减少空间复杂度
23
        ++right[ s[k] ];
24
    }
25
    return max(longestSubString(beg,j,right),
26
                longestSubString(j+1,end,imap));
27
}

有一点要注意的就是：如果是使用map而不是unordered_map的话，时间是会超限的。

然后是在dicuss中看到的解法：

下面这个的解法和我的类似，他的会比较简洁，不过应该没我的快，因为他每次都需要递归都是直接传递string的，而且调用s.substr其实挺耗费时间的，应该每次都是深拷贝。

1
int longestSubstring(string s, int k) {
2
        if(s.size() == 0 || k > s.size())   return 0;
3
        if(k == 0)  return s.size();
4
        unordered_map<char,int> Map;
5
        for(int i = 0; i < s.size(); i++){
6
            Map[s[i]]++;
7
        }
8
        int idx =0;
9
        while(idx <s.size() && Map[s[idx]] >= k)    idx++;
10
        if(idx == s.size()) return s.size();
11
        int left = longestSubstring(s.substr(0 , idx) , k);
12
        int right = longestSubstring(s.substr(idx+1) , k);
13
        return max(left, right);
14
    }

第二个是用迭代的方法做的，比较快点，但是好像最坏情况是会出现O(n^2)的时间复杂度：

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

13
           if (mask == 0) {
14
               max_len = max(max_len, last-first+1);
15
               max_last = last;
6 collapsed lines
16
           }
17
       }
18
       first = max_last + 1;
19
   }
20
   return max_len;
21
}