每日一题 395 (滑动数组/递归)

395. 至少有 K 个重复字符的最长子串

给你一个字符串 s 和一个整数 k ,请你找出 s 中的最长子串, 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

输入:s = "aaabb", k = 3
输出:3

思路
  • 采用递归的方式计算最长子串(需要是连续的)
  • 如果某个字符次数小于k,则所有包含它的都不满足,可以划分
class Solution {
public:
    int longestSubstring(string s, int k) {
        if (s.size() < k) {
            return 0;
        }
        unordered_map<char, int> um;
        for (int i = 0; i < s.size(); i++) {
            um[s[i]]++;
        }
        unordered_set chars(s.begin(), s.end());
        for (char c : chars) {
            vector<string> t;
            if (um[c] < k) {
                split(s, t, c);
                int res = 0;
                for (string st : t) {
                    res = max(res, longestSubstring(st, k));
                }
                return res;
            }
        }
        return s.size();
    }
    void split(const string &s, vector<string> &sv, char flag = ' ') {
        sv.clear();
        istringstream iss(s);
        string temp;
        while (getline(iss, temp, flag)) {
            sv.push_back(temp);
        }
    }
};

评论

暂无评论