Formatted question description: https://leetcode.ca/all/424.html

424. Longest Repeating Character Replacement

Level

Medium

Description

Given a string s that consists of only uppercase English letters, you can perform at most k operations on that string.

In one operation, you can choose any character of the string and change it to any other uppercase English character.

Find the length of the longest sub-string containing all repeating letters you can get after performing the above operations.

Note:

Both the string’s length and k will not exceed 104.

Example 1:

Input:

s = “ABAB”, k = 2

Output:

4

Explanation:

Replace the two ‘A’s with two ‘B’s or vice versa.

Example 2:

Input:

s = “AABABBA”, k = 1

Output:

4

Explanation:

Replace the one ‘A’ in the middle with ‘B’ and form “AABBBBA”.

The substring “BBBB” has the longest repeating letters, which is 4.

Solution

Use sliding window. Use a map to store each letter and the number of occurrences of each letter. Initialize low and high to 0, and use maxCount to store the maximum numbers of the same letter met so far, which is initially 0.

Loop over s using index high. Obtain the letter at index high, update the number of occurrences of the letter in the map, and update maxCount. If the current substring’s length high - low + 1 is greater than maxCount + k, then move low forward by 1 step. Move high forward by 1 step after the letter is dealt with. Finally, return s.length() - low.

  • class Solution {
        public int characterReplacement(String s, int k) {
            if (s == null || s.length() == 0)
                return 0;
            Map<Character, Integer> map = new HashMap<Character, Integer>();
            int maxCount = 0;
            int low = 0, high = 0;
            int length = s.length();
            while (high < length) {
                char highC = s.charAt(high);
                int highCount = map.getOrDefault(highC, 0);
                highCount++;
                map.put(highC, highCount);
                maxCount = Math.max(maxCount, highCount);
                if (high - low + 1 > maxCount + k) {
                    char lowC = s.charAt(low);
                    int lowCount = map.getOrDefault(lowC, 0);
                    lowCount--;
                    if (lowCount > 0)
                        map.put(lowC, lowCount);
                    else
                        map.remove(lowC);
                    low++;
                }
                high++;
            }
            return length - low;
        }
    }
    
  • // OJ: https://leetcode.com/problems/longest-repeating-character-replacement/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        int characterReplacement(string s, int k) {
            int i = 0, j = 0, cnt[26] = {}, ans = 0, N = s.size();
            while (j < N) {
                cnt[s[j++] - 'A']++;
                while (j - i - *max_element(cnt, cnt + 26) > k) cnt[s[i++] - 'A']--;
                ans = max(ans, j - i);
            }
            return ans;
        }
    };
    
  • from collections import deque
    
    
    class Solution(object):
      def characterReplacement(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        ans = 0
        d = {}
        start = 0
        maxCount = 0
        window = deque([])
        for end in range(0, len(s)):
          d[s[end]] = d.get(s[end], 0) + 1
          maxCount = max(maxCount, d[s[end]])
          if end - start + 1 - maxCount > k:
            d[s[start]] -= 1
            start += 1
          ans = max(ans, end - start + 1)
        return ans
    
    

All Problems

All Solutions