【leetcode】 395 Longest Substring with At Least K Repeating Characters

发表于 | 分类于 ，

超过 k 次的最长序列


描述

给定一个数组以及一个整数 k ，需要找到一个最长的子序列，这个子序列中的每一个字符在该子序列中都超过了 k 次,输出这个子序列的长度。

样例

1
2
输入: "bbaaacbd",3
输出: 3

思路

有点类似求最大子序列的的和，有 2 种方法可以考虑，第一种：两重循环遍历，i 到 j，假设 i 为子序列的开始，j 为子序列的结束，这种方法思路简单，但是效率很低下。第二种，采用分治法: 想办法将这个序列切分成多段。本题可以这么考虑，一个数组要么全部数字可以满足条件，要么就是不满足，不满足肯定是某个数字造成的影响，这个数字也就是最不频繁的那个数字了。根据这个数字将数组分成多段序列，然后对这多段序列分别计算，求出最大值。

代码

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
42
43
44
45
46
47
48
49
class Solution {
public:
    int longestSubstring(string s, int k) {
        unordered_map<char, int> m;
        int len = s.size();
        if (len < k) { return 0; }
        for (int i = 0; i < len; i++) {
            m[s[i]]++;
        }
        int ok = true;
        for (auto c : m) {
            if (c.second < k) {
                ok = false;
                break;
            }
        }
        if (ok) { return len; }
        char nc;
        int minnum = INT_MAX;
        for (auto iter = m.begin(); iter != m.end(); iter++) {
            if (iter->second < minnum) {
                minnum = iter->second;
                nc = iter->first;
            }
        }
        vector<string> vecstr;
        spiltstr(s, nc, vecstr);
        int result = vecstr.empty()?0:longestSubstring(vecstr[0],k);
        for (int i = 1; i < vecstr.size(); i++) {
            result = std::max(result, longestSubstring(vecstr[i], k));
        }
        return result;
    }

    void spiltstr(string s, char c, vector<string> & vecstr) {
        vecstr.clear();
        string tempstr="";
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != c) { tempstr += s[i]; }
            else {
                if(tempstr!=""){
                    vecstr.push_back(tempstr);
                    tempstr = "";
                }
            }
        }
        if(tempstr!=""){ vecstr.push_back(tempstr); }
    }
};

分词可以参考这个代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline void split(const string &s, char delim, vector<string> &elems) {
    stringstream ss;
    ss.str(s);
    string item;
    while (getline(ss, item, delim)) {
        cout << item << endl;
        elems.push_back(item);
    }
}


inline vector<string> split(const string &s, char delim) {
    vector<string> elems;
    split(s, delim, elems);
    return elems;
}

推荐代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestSubstring(string s, int k) {
        if (s.empty()) return 0;
        unordered_map<char, int> count;
        for (auto c : s) count[c]++;

        int max_length = 0;
        int pre = 0;
        for (int i = 0; i<s.size(); i++) {
            if (count[s[i]]<k) {
                if (pre != i) {
                    max_length = max(max_length, longestSubstring(s.substr(pre, i - pre), k));
                }
                pre = i + 1;
            }
        }
        max_length = max(max_length, (int)(pre == 0 ? s.size() : longestSubstring(s.substr(pre), k)));
        return max_length;
    }
};

参考

原题链接