another way to solve .diffierent from sliding window


  • 0
    Y
    const int maxn = 1e4 + 5;
    int m[maxn];
    
    class Solution {
    public:
        int characterReplacement(string s, int k) {
            int ans = -1, N = s.size();
            for(char c = 'A'; c <= 'Z'; c++){
                int cnt = 0;
                for(int i = 0; i < N; i++){
                    if(s[i] != c) cnt ++;
                }
                if(cnt <= k) return N;
                ans = max(ans, longest(s, c, k));
            }
            return ans;
        }
    
        int longest(string& s, char c, int k){
            int N = s.size(), ans = -1;
            memset(m, -1, sizeof(m));
            m[0] = 0;
            int cnt = 0;
            for(int i = 1; i <= N; i++){
                if(s[i - 1] != c) cnt ++;
                if(m[cnt - k] != -1) ans = max(ans, i - m[cnt - k]);
                if(m[cnt] == -1) m[cnt] = i;
            }
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.