MENU

LeetCode395. Longest Substring with At Least K Repeating Characters(递归 / 分治)

2019 年 04 月 17 日 • 阅读: 1477 • LeetCode阅读设置

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日 星期三