LC 424 - Longest Repeating Character Replacement

Question

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

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.
There may exists other ways to achieve this answer too.

Constraints:

• 1 <= s.length <= 105
• s consists of only uppercase English letters.
• 0 <= k <= s.length

Links

Question here and solution here

Solution

concept

The main concept is to understand that we can check window - max freq of char in window < k. This is because this gives us the number of char that is not the most frequently occured which we should replace.
We use a dictionary to keep track the char frequency count and at each step we will need to iterate through this dict to get the max value inside.

code

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
	    """
	    sliding window
	    checking
	    """
        l, r = 0, 0
        ans = 0
        char_map = defaultdict(int)
        max_freq = 0

        while r < len(s):
            char_map[s[r]] += 1
            max_freq = max(max_freq, char_map[s[r]])

            if (r - l + 1) - max_freq <= k:
                ans = max(ans, r - l + 1)
                r += 1
            else:
                while (r - l + 1) - max_freq > k:
                    char_map[s[l]] -= 1
                    l += 1
                r += 1  # move r forward after shrinking

        return ans


class NeetSolution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        res = 0

        l = 0
        for r in range(len(s)):
            count[s[r]] = 1 + count.get(s[r], 0)

            while (r - l + 1) - max(count.values()) > k:
                count[s[l]] -= 1
                l += 1

            res = max(res, r - l + 1)
        return res

Complexity

time: $O(26n)$
space: $O(26)$