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.
A:
就是挨个数,如果某个字母不满足,则将其前后分开。递归 (pass)
class Solution { public: int longestSubstring(string s, int k) { if(s.length()<k) return 0; // return 0 if does not contains such a string vector<int> C(26,0); for(auto ch : s) C[ch-'a']++; for(int i =0;i<s.length();++i) { int count = C[s[i]-'a']; if((count>0 and count < k)) // if not include this letter, exclude it and { int tmp = longestSubstring(s.substr(0, i), k ); // will omit the last substring int tmp2 = longestSubstring(s.substr(i+1), k ); // will omit the last substring return max(tmp, tmp2); } } return s.length(); } };
Time complexity:O(N*lg(N))
改进算法:
Approach 2 : Sliding Window
Complexity
Time complexity:O(N)
Space complexity:O(1)
No comments:
Post a Comment