O(N*alphabetSize) two pointers


  • 2
    A

    Lets try to simplify the problem and try to solve it for one letter('A'). To solve that problem we can use two pointers. Each time we will try to move our right pointer. We can move it in two cases:

    1. if the s[right]=='A'
    2. if the s[right]!='A' and there is enough K to replace the character with 'A';
      We will move left if there isn't anymore K to replace any character at position [right].
      Each time we should track the number of replacements we did. When we move left we need to decrease using number of replacements if s[left]!='A';
      The answer will be range between left and right;

    If we will solve this problem for each letter then we can find maximum amoung their maximum length's

    public class Solution {
        public int characterReplacement(String s, int k) {
            int max = 0;
            for (char i='A'; i<='Z'; i++) {
                int L = 0;
                int R = 0;
                int cnt = 0;
                while (R<s.length()) {
                    if (s.charAt(R)==i) {
                        R++;
                    } else {
                        if (cnt<k) {
                            R++;
                            cnt++;
                        } else {
                            if (s.charAt(L)!=i) {
                                cnt--;
                            } 
                            L++;
                        }
                    }
                    max = Math.max(max, R-L);
                }
            }
            return max;
        }
    }
    

  • 0
    Z

    Hi Aman! Here I have both binary search and two pointers methods. Idea is the same, great people think similar:=)

    public class Solution {
        
        public int characterReplacement(String s, int k) {
            if(k>=s.length()) return s.length();
            int res = k;
            char w[] = s.toCharArray();
            for(char cur = 'A';cur<='Z';cur++){
                res = Math.max(res, findMax2Ptr(cur, w, k));
            }
            return res;
        }
        
        private int findMax2Ptr(char ch, char [] w, int k){
            int res = 0;
            int i = 0, j = 0;
            while(j<w.length ){
                if(ch == w[j]){
                    j++;
                    res = Math.max(res, j-i);
                    continue;
                } 
                if(k == 0){
                    if(w[i] != ch){
                        k++;
                    }
                    i++;
                } else {
                    k--;
                    j++;
                }
                res = Math.max(res, j-i);
            }
            return Math.max(res, j-i);
        }
        
        private int findMaxBinary(char ch, char [] w, int k){
            int l = 0;
            int r = w.length;
            int res = 0;
            while(l<=r){
                int m = (l+r)/2;
                if(countMinGaps(w, m, ch) <= k){
                    res = m;
                    l = m+1;
                } else {
                    r = m-1;
                }
            }
            return res;
        }
        
        private int countMinGaps(char w[], int size, char ch){
            int count = 0;
            int i = 0;
            int res = size;
            while(i<w.length){
                if(i<size){
                    if(w[i] !=ch) {
                        count++;
                    }
                } else {
                    res = Math.min(res, count);
                    if(w[i-size] != ch){
                        count--;
                    } 
                    if(w[i] != ch) {
                        count++;
                    }
                }
                i++;
            }
            return Math.min(count,res);
        }
       
        
    }

Log in to reply
 

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