Problem Statement in English

You’re given a string s, and an integer k.

Your task is to determine the longest substring in s built of the same character. You’re allowed to replace any k characters from the substring with any letter you like, in order to meet the requirement.

Approach

Brute forcing this is definitely an option, but we can do better. Hence we won’t go into the nested loop approach.

We’ll cover the linear time approach that uses the Sliding Window technique with a dynamic window size. The mechanics of this approach have been discussed in this problem.

However, this problem needs us to build upon that base model.

In particular, we need a mechanism to keep track of whether we can ensure that all characters in the window are the same character. This sounds way harder than it actually is.

First off, we need to maintain the frequency of each character occuring in the current window. A frequency map. I’ve called this the registry.

Secondly, we need to check if we can convert all character in the window to be the same character. The way we do this, is by using that frequency map, and checking if the the difference between all frequencies and the frequency of the highest occuring value is lesser <= k.

Why?

This is because the value with the highest frequency is what we’d replace all other characters with. So we need to check if we’ve our replacement allowance provides for us to replace every other character with the highest occuring one.

Solution in Python


class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # tracks longest substring
        # that satisfies the requirements
        ans = 0

        # tracks frequency of characters
        registry = {}

        # left pointer
        l = 0

        # move right pointer forward
        for r in range(len(s)):
            # update frequency map
            # based on new character
            # pointed to by right pointer
            if s[r] in registry:
                registry[s[r]] += 1
            else:
                registry[s[r]] = 1

            # while we can't replace all characters
            # in the window to be the same character
            while (r - l + 1) - max(registry.values()) > k:
                # since we're going to move the left pointer forward,
                # the frequency contribution by the character
                # pointed to by left must be decremented
                registry[s[l]] -= 1

                # compaction, this is optional
                # helps if there's a lot of distinct characters in the string
                #
                # actually no...just realized there can only be 26 ;(
                # sighh
                if registry[s[l]] == 0:
                    del registry[s[l]]

                # move left pointer forward
                l += 1

            # update the longest length substring,
            # if need be
            ans = max(ans, r - l + 1)

        # return answer
        return ans

Complexity

  • Time: O(n)O(n)
    Since we process nn elements at most.

  • Space: O(n)O(n)
    Since we store nn elements at most in the Map.

Mistakes I Made

I used the following condition in the while loop:

while sum(registry.values()) - max(registry.values()) > k:

instead of

while (r - l + 1) - max(registry.values()) > k:

🤦‍♂️.

And we are done.