Longest Repeating Character Replacement

mediumFREESliding WindowBlind 75

Given a string s and an integer k, you can choose any character and change it to any other uppercase English letter at most k times.

Return the length of the longest substring containing the same letter after performing at most k replacements.

Example

Input

AABABBA
1

Output

Reasoning

We start with the input string AABABBA and the replacement limit k = 1.
We try to find the longest substring with the same letter after at most k replacements. The substring AABBB can be formed by replacing one A with a B, resulting in a substring of length $4$ with the same letter B if we consider AABBB as BBBB after replacement, but since we are considering AABABBA we look at AABB and BBBA and see AABB can become AAAA or BBBB with one replacement.
Considering all possible substrings, we find that the longest one with the same letter after at most 1$ replacement is of length $4$, which can be achieved by replacing one character in AABBto getAAAAor inBBBAto getBBBB`.
The final output is $4$ .

Constraints

1 <= len(s) <= 10^5
s consists of uppercase English letters
0 <= k <= len(s)

Learn this in

Two Pointers & Sliding WindowDSA Study Plan

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The "Longest Repeating Character Replacement" problem falls under the Sliding Window technique, a popular approach in string and array problems. The Sliding Window technique involves creating a window that moves over the data structure, expanding or shrinking it based on certain conditions. This technique is useful for problems that require finding a subset of data that meets specific criteria. In the context of this problem, the Sliding Window will help us find the longest substring that can be made to contain the same letter after at most k replacements.

To understand this problem, it's essential to have a good grasp of string manipulation and frequency counting. We need to keep track of the frequency of each character within the current window and adjust the window boundaries based on the number of replacements allowed. The problem also involves maximization, as we want to find the longest possible substring that meets the condition. This requires us to keep track of the maximum length of the substring seen so far.

The problem can be broken down into smaller sub-problems, such as finding the frequency of characters within a window, checking if the number of replacements is within the limit, and adjusting the window boundaries accordingly. This divide-and-conquer approach will help us tackle the problem in a more manageable way.

Algorithm/Approach

The general approach to solve this problem involves using a Sliding Window with two pointers, left and right, to represent the boundaries of the window. We will also use a frequency dictionary to keep track of the frequency of each character within the current window. The algorithm will iterate over the string, expanding the window to the right and shrinking it from the left as needed to maintain the condition of at most k replacements.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize two pointers, left and right, to represent the boundaries of the window.
Create a frequency dictionary to store the frequency of each character within the current window.
Iterate over the string, expanding the window to the right by moving the right pointer.
For each character, update the frequency dictionary and check if the number of replacements is within the limit.
If the number of replacements exceeds the limit, shrink the window from the left by moving the left pointer and update the frequency dictionary accordingly.
Keep track of the maximum length of the substring seen so far.

Common Pitfalls

When implementing the solution, watch out for the following:

Incorrectly updating the frequency dictionary when expanding or shrinking the window.
Failing to check if the number of replacements is within the limit before expanding the window.
Not keeping track of the maximum length of the substring seen so far.

Time & Space Complexity

The expected time complexity for this problem is O(n), where n is the length of the string, since we are iterating over the string once. The space complexity is O(1), as we are using a frequency dictionary with a fixed size (26 uppercase English letters) to store the frequency of each character.

solution.py

Python 3.13

Test results