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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        from collections import defaultdict

        max_freq = 0 # Frequency of the most common character in the current window
        freq_counter = defaultdict(int) # Frequency counter for characters in the window
        left = 0 # Left pointer
        max_length = 0 # Result for the maximum length of the substring

        for right in range(len(s)): # Move the right pointer
            char = s[right]
            freq_counter[char] += 1
            max_freq = max(max_freq, freq_counter[char])

            # Check if the current window needs more than k replacements
            if right - left + 1 - max_freq > k:
                freq_counter[s[left]] -= 1
                left += 1

            # Update the result
            max_length = max(max_length, right - left + 1)

        return max_length

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int characterReplacement(string s, int k)
    {
        int start = 0, end = 0, max_char = 0, length = 0;
        vector<int> freq(26, 0);
        int n = s.size();

        for(int end=0;end<n;end++)
        {
            freq[s[end]-  'A']++;
            int x = freq[s[end] - 'A'];

            max_char = max(max_char, x);

            while(end-start+1-max_char > k)
            {
                freq[s[start] - 'A']--;
                start++;
            }

            length = max(length, end-start+1);
        }

        return length;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# @param {String} s
# @param {Integer} k
# @return {Integer}
def character_replacement(s, k)
#     i is the left index of the string
   i = 0
#     j is the right index of the string
   # j = 0
#     Keep track of the character that is the highest frequency
#     we have encountered so far
   max_char = 0
#     The final answer
   length = 0
   freq = Array.new(26, 0)
   n = s.size

    for j in (0...n)
      freq[s[j].ord - 'A'.ord] += 1
      x = freq[s[j].ord - 'A'.ord]
      max_char = [max_char, x].max

      while(j - i+1 - max_char > k)
         freq[s[i].ord - 'A'.ord] -= 1
         i += 1
      end
       length = [length, j - i + 1].max
    end

    return length
end

layout: post title: Longest Repeating Character Replacement excerpt: This covers the basic building blocks such as Two Pointers, Frequency Counter and Find Maximum. tags: two-pointers frequency-counter find-maximum sliding-window 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def character_replacement(s, k)
  ascii_a = 'A'.ord
  # i is the left index of the string
  i = 0
  # Keep track of the character that is the highest frequency
  # we have encountered so far
  max_char = 0
  # The final answer
  length = 0
  freq = Array.new(26, 0)
  n = s.size
    
  for j in (0..n-1)
    freq[s[j].ord - ascii_a] += 1
    x = freq[s[j].ord - ascii_a]
    
    max_char = [max_char, x].max
       
    while(j - i+1 - max_char > k)
      freq[s[i].ord - ascii_a] -= 1
      i += 1
    end
    
    length = [length, j - i + 1].max
  end
    
  return length
end

Invariant is a condition that should never change during the execution of a program.

Building Blocks

Two Pointers
Frequency Counter
Find Maximum
Sliding Window