leetcode 424. Longest Repeating Character Replacement | 424. 替换后的最长重复字符（Java）

青旅半醒 2022-09-03 13:22 38阅读 0赞

## 题目 ##

[https://leetcode.com/problems/longest-repeating-character-replacement/][https_leetcode.com_problems_longest-repeating-character-replacement]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

class Solution { 
        public int characterReplacement(String s, int k) { 
            HashSet<Character> seen = new HashSet<>();
            int max = 0;
            for (int i = 0; i < s.length(); i++) { 
                if (!seen.contains(s.charAt(i))) { 
                    seen.add(s.charAt(i));
                    int L = 0;
                    int R = -1;
                    int curK = 0;
                    while (R < s.length()) { 
                        while (R < s.length() && curK <= k) {  // R肯定在_上，且不包含_
                            R++;
                            if (R < s.length() && s.charAt(R) != s.charAt(i)) curK++;
                        }
                        max = Math.max(max, R - L); // 左闭右开区间
                        while (L <= R && curK > k) {  // 肯定在A上，且包含A
                            if (s.charAt(L) != s.charAt(i)) curK--;
                            L++;
                        }
                    }
                }
            }
            return max;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_longest-repeating-character-replacement]: https://leetcode.com/problems/longest-repeating-character-replacement/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/60e28a08f913454683d1dee276382277.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/ee94ccf3dcd24ee2b654d1b7c94589f2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/a408dcb4fc1b47c793881f40c590acaa.png