新姿势暴力过LeetCode 395. Longest Substring with At Least K Repeating Characters


这道题最优解法应该是O(n)的,一开始没想到,就这么暴力也AC了,看网上博客O(n^2)是过不了的,我优化的好?
class Solution {
public:
    int longestSubstring(string s, int k) {
        if (s.size() == 0 || k > s.size()){
            return 0;
        }
        if (k == 1 || k == 0){
            return s.size();
        }
        
        int curLen = 0, maxLen = 0;
        int ch[26];
        
        for (int i = 0; i < s.size(); ++i){
            memset(ch, 0, sizeof(ch));
            for (int j = i; j < s.size(); ++j){
                ch[s[j] - 'a']++;
                if (isTrue(ch, k)){
                    maxLen = max(maxLen, j - i + 1);
                }    
            }
        }
        
        return maxLen;
    }
    
    bool isTrue(int ch[26], int k){
        for (int i = 0; i < 26; ++i){
            if (ch[i] == 0) continue;
            if (ch[i] < k) return false;
        }
        return true;
    }
    
};
已邀请:

要回复问题请先登录注册

返回顶部