Longest Repeating Character Replacement
The problem is to find the length of the longest substring containing the same letter after performing at most ( k ) operations, where each operation consists of changing any character to any other uppercase English character.
We can solve this problem using a sliding window technique:
 Initialize Two Pointers: Create two pointers, ( \text{left} ) and ( \text{right} ), initialized to the beginning of the string.
 Create Frequency Counter: Maintain a frequency counter to keep track of the frequency of characters in the current window.
 Expand the Window: Move the right pointer to the right, expanding the window.
 Calculate Replacements: Calculate the number of replacements needed to make all characters in the current window the same. This can be calculated as the size of the current window minus the frequency of the most common character in the window.
 Shrink the Window: If the number of replacements needed is greater than ( k ), move the left pointer to the right, shrinking the window.
 Update the Result: Keep track of the maximum size of the window that meets the requirements, i.e., the number of replacements needed is less than or equal to ( k ).
 Continue Iterating: Continue moving the right pointer and adjusting the left pointer as necessary until the right pointer reaches the end of the string.
Here’s the code:


The above code implements the sliding window technique to find the longest substring with the same letters after performing at most ( k ) replacements. It works within the given constraints and has a time complexity of ( O(n) ), where ( n ) is the length of the input string.
=begin
Define the Terms Longest repeating character: substring with same character
Define the Interface Input: string s, integer k Output: integer
Analyze the Input and Output
Example 1: The substring, AAAA or BBBB
ABAB => Replace B with A twice ABAB => Replace A with B twice
Identify the Invariants
Identify the constraints We cannot have more than k replacements
Search the Problem Space
Classify the Problem
Analyze the Examples
Solve the Problem by Hand Find the frequency of A and B A => 2 B => 2
“AABABBA”
‘AABABADDDDD’, k = 2
=> 6 => 4 => 7
Start index and the end index. We don’t know where we need to start replacements to find the maximum repeating characters
Position of the replacment matter when we form the string with k replacements with repeating characters.
Find the substring that has length at most k+1.
Do we need a frequency counter or not?
AABABBA
A => 4 B => 3 k = 1
Instead of storing the frequency of the letters, we can store the number of letters that repeating as a substring.
Just because the longest substring contains the same character does not mean we can scan from left to right in that substring to replace and find the answer for longest repeating strings
‘REPLACEELARB’, k = 4
Take an example which is an extreme case, create an example with highest frequency character for A. Express the invariant as the loop termination condition.
Describe the Pattern
Distill the Observations to Create Insights
Brute Force Approach
Analyze Time and Space Complexity
Outline the Solution
Key Takeaways




layout: post title: Longest Repeating Character Replacement excerpt: This covers the basic building blocks such as Two Pointers, Frequency Counter and Find Maximum. tags: twopointers frequencycounter findmaximum slidingwindow invariant
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.
Constraints
 1 <= s.length <= 105
 s consists of only uppercase English letters.
 0 <= k <= s.length
This problem is similar to Max Consecutive Ones III.
Define the Term
Longest repeating character: substring with same character
Define the Interface
Input: string s, integer k Output: integer
Analyze the Input and Output
Example 1: The substring, AAAA or BBBB
ABAB => Replace B with A twice ABAB => Replace A with B twice
The constraint is that we cannot have more than k replacements
Find the frequency of A and B
A => 2 B => 2
“AABABBA”
‘AABABADDDDD’, k = 2
=> 6 => 4 => 7
We need a start index and an end index. We don’t know where we need to start replacements to find the maximum repeating characters. Position of the replacement matter when we form the string with k replacements with repeating characters. Find the substring that has length at most k+1. Do we need a frequency counter or not?
AABABBA
A => 4 B => 3 k = 1
Instead of storing the frequency of the letters, we can store the number of letters that repeat as a substring. Just because the longest substring contains the same character does not mean we can scan from left to right in that substring to replace and find the answer for longest repeating strings
‘REPLACEELARB’, k = 4
Take an example which is an extreme case, create an example with the highest frequency character for A. Express the invariant as the loop termination condition.
Implementation


Invariant is a condition that should never change during the execution of a program.
Building Blocks
 Two Pointers
 Frequency Counter
 Find Maximum
 Sliding Window