Leetcode 424) Longest Repeating Character Replacement

28 Oct 2021 in Algorithms

My Answer

• we have 2 pointers , left and right. Thinking about WHEN we update left one, or right one helps a lot to expand the logic.
  • move right pointer when smaller than k+maxCnt.
  • move left pointer and right pointer together when bigger than k+maxCnt. (Basically, we are sliding the window towards the end. the window size won’t decrease. )

class Solution {
    public int characterReplacement(String s, int k) {
        int left =0; int right = 0;
        int maxCnt=1;
        Map<Character , Integer> m = new HashMap<>();
        while(right < s.length() && right - left <= k+maxCnt){
            char cur = s.charAt(right);
            if(m.containsKey(cur)){
                m.put(cur,m.get(cur)+1);
                //위에서 m.get(cur)값 하나 증가했으니까, 아래는 이렇게 부르면 된다. 
                if(m.get(cur)>maxCnt){
                    maxCnt = m.get(cur);
                }
            }else{
                m.put(cur, 1);
            }
            right ++;

            while(right - left > k+maxCnt){
                char old = s.charAt(left);
                m.put(old,m.get(old)-1);
                left++;
            }
        }
        //k+maxcount 는 s.length()보다 큰값이 나올 수 있다.
        return right-left;
    }
}

Different Answer

class Solution {
    public int characterReplacement(String s, int k) {
        if (s.length() == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int [] charArr = new int[26];
        int maxCount = 0;
        int maxLength = 0;
        int start = 0;
        for (int end = 0; end < s.length(); end++) {
            charArr[s.charAt(end) - 'A']++;
             maxCount = Math.max(maxCount, charArr[s.charAt(end) - 'A']);
            while ((end - start + 1) - maxCount  > k) {
                charArr[s.charAt(start) - 'A']--;
                start++;
            }
            maxLength = Math.max(maxLength, end - start + 1);
        }
        return maxLength;
    }
}