题目

给定一个字符串s和一个整数k, 找出s中每个字符重复不少于k次的最长子字符串.

Input: "aaabb", 3
Output: 3
Input: "ababbc", 2
Output: 5

思路1

分治(divide and conquer). 将字符串拆分为小字符串, 遇到不达标的地方就拆分成两段.

int longestSubstring(string s, int k) {
    int n = (int)s.size();
    if (n < k) return 0;

    vector<int> vec(26, 0);
    for(char c : s) {
        vec[c - 'a']++;
    }

    int pos = 0;
    while (pos < n) {
        if (vec[s[pos]-'a'] < k) {
            break;
        }
        pos++;
    }
    if (pos == n) return n;

    int left = longestSubstring(s.substr(0,pos), k);
    while (pos < n) {
        if (vec[s[pos]-'a'] < k) {
            pos++;
        } else {
            break;
        }
    }
    int right = longestSubstring(s.substr(pos), k);
    return max(left, right);
}

思路2

笨方法. 效率低. 将字符串分割成不同区域, 然后计算该区域是否达标, 重复计算比较多.

int longestSubstringCount(string& s, char c, int l, int r) {
    int res = 0;
    for(int i = l;i <= r;i++) {
        if (s[i] == c) {
            res++;
        }
    }
    return res;
}

int longestSubstring(string s, int k) {
    int res = 0;
    vector<int> vec(26, 0);
    for(char c : s) {
        vec[c-'a']++;
    }

    for (int l = 0;l < s.size();l++) {
        if(vec[s[l]-'a'] < k) {
            continue;
        }
        for (int r = (int)s.size()-1; r >= l+k-1;r--) {
            if (r - l + 1 < res || vec[s[r]-'a'] < k) {
                continue;
            }
            //cout << "l : " << l << " r: " << r <<endl;
            bool isOK = true;
            for (int i = l;i <= r; i++) {
                if (vec[s[i]-'a'] < k || longestSubstringCount(s,s[i],l,r) < k) {
                    isOK = false;
                    break;
                }
            }
            if (isOK) {
                res = r - l + 1;
            }
        }
    }

    return res;
}

总结

分治思想很重要, 如何分治有需要具体分析.