Longest Repeating Character Replacement

LeetCode

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.

Initial attempt

Time spent: 1h 20m | Runtime: 87.80% | Memory: 80.26%

• The performance numbers are misleading since they were achieved after looking at the solution.
• I tried looking at character counts but it wasn't immediately clear what I needed to do. This felt like dynamic programming, but I couldn't identify the recurrence relation and spent a lot of time looking for it.
• There seemed to be another subproblem, but it simultaneously could not be solved and did not need to be solved to find a solution to this problem.

Given a window [start, end], a count dict of the characters, and the frequency of the most common character, how can we evaluate those same values for [start + 1, end]?

We don't need to solve this problem since the size of the window never needs to decrease. We're constantly looking to expand the window and may encounter "invalid" windows in our search.

Intuition

• Any letter can achieve a max repeating length of at least k by changing k consecutive letters to that target.
• If there are m instances of a given character in a substring of length k + m, the entire substring can be turned into the given character.

Solution

• Start with a window of size k + m where m is the frequency of the most common letter in that substring. Also keep count along the way.
• This window slides to the right (i.e. both start and end move) unless a new character encountered allows the window to expand.

Cleaned up code

Time spent: 8m | Runtime: 77.37% | Memory: 99.42%

import collections


class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        counts = collections.defaultdict(int)
        start = 0
        most_frequent = 0
        longest_length = 0
        for end in range(len(s)):
            counts[s[end]] += 1
            most_frequent = max(most_frequent, counts[s[end]])

            # If window size is greater than allowed, contract it.
            if end - start + 1 > most_frequent + k:
                counts[s[start]] -= 1
                start += 1

            longest_length = max(longest_length, end - start + 1)
        return longest_length