[LeetCode 395] Longest Substring with At Least K Repeating Characters

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.

分析

暴力搜索的办法可以解决这个问题，时间复杂度为O(n^2)。但是看到讨论区中有一个更好的办法可以使用分治的算法取得更好的时间复杂度。

以abcaba， k=2距离，首先使用int[26]数组记录字符出现的次数，那么a=3, b=2, c=1，此时c是不满足条件的，那么可以确定最终的字符中一定不会包含字符c，那么就在string的范围中找到字符c，分别在其左右继续寻找最大的长度。那么就是ab, aba，这样就可以找到最长的aba。

Code

class Solution { public: int longestSubstring(string s, int k) { int len = s.size(); return findString(s, 0, len-1, k); } int findString(const string& s, int start, int end, int k) { if (end - start < k - 1) return 0; int cnt[26] = {0}; for (int i = start; i <= end; i ++) { cnt[s[i] - 'a'] ++; } for (int i = 0; i < 26; i ++) { if (cnt[i] > 0 && cnt[i] < k) { char c = i + 'a'; for (int j = start; j <= end; j ++) { if (s[j] == c) { int left = findString(s, start, j-1, k); int right = findString(s, j+1, end, k); return max(left, right); } } } } return end-start + 1; } };

运行效率 

Runtime: 156 ms, faster than 35.79% of C++ online submissions for Longest Substring with At Least K Repeating Characters.

Memory Usage: 12.8 MB, less than 25.59% of C++ online submissions for Longest Substring with At Least K Repeating Characters.