LeetCode395. Longest Substring with At Least K Repeating Characters（递归 / 分治）

Medium
Accepted：44,673
Submissions：116,562

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.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

链接

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters

题意

给定一个只包含小写字母的字符串，找到其中最长的子串T，满足T中的每个字符的出现次数都不小于k。

题解

题目要求子串T中每个字符的出现次数都不小于k，然后又只包含小写字母，我们我们可以先用一个数组统计其中每个字符出现的次数，如果某个字符出现次数小于k，那么这个字符肯定不在我们要求的子串中，所以我们可以以该字符作为分界线，对左边子串和右边子串做递归处理。

对于递归返回的条件，如果当前字符串长度n小于k，那么返回0，如果当前字符串中所有的字符出现次数都大于k，那么返回n。

时间复杂度：$T(n) = 2T(n/2) + n$，为$O(nlogn)$，具有较大的常数。

代码

Runtime: 176 ms, faster than 34.60% of C++ online submissions for Longest Substring with At Least K Repeating Characters.
Memory Usage: 54.7 MB, less than 23.08% of C++ online submissions for Longest Substring with At Least K Repeating Characters.

class Solution {
private:
    int solve(string s, int k)
    {
        int n = s.length();
        if (n < k)
            return 0;
        int cnt[26] = {0};
        for (int i = 0; i < n; ++i)
            cnt[s[i] - 'a']++;
        int mid = 0;
        while (mid < n && cnt[s[mid] - 'a'] >= k)
            ++mid;
        if (mid == n)
            return n;
        int left = solve(s.substr(0, mid), k);
        int right = solve(s.substr(mid + 1), k);
        return max(left, right);
    }
public:
    int longestSubstring(string s, int k) {
        return solve(s, k);
    }
};

The end.
2019年4月17日星期三