Solution: Longest Repeating Character Replacement

Statement

Given a string, s, and an integer, k, find the length of the longest substring in s, where all characters are identical, after replacing, at most, k characters with any other uppercase English character.

Constraints:

• $1 \leq$ s.length $\leq 10^3$

• s consists of only uppercase English characters.

• $0 \leq$ k $\leq$ s.length

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

A brute force method checks every possible substring to see if it can be transformed into a string of identical characters with at most k replacements. Here’s how it works:

• Consider every substring starting from that character for each character in the string.

• For each substring, use a nested loop to count the number of replacements needed to make all its characters identical.

• If the number of replacements is within the allowed limit k and the substring is longer than any previously found valid substring, update the longest length.

This method uses three nested loops—one to choose the starting point, one to choose the ending point, and one to calculate the required replacements—resulting in a time complexity of $O(n^3)$, where $n$ is the length of the input string.

Optimized approach using sliding window

We have to find the maximum length of a substring where we can replace up to k characters to make all characters in the substring identical. To solve this efficiently, we use the sliding window approach. It involves two pointers marking the start and end of a segment that moves across the main string. This method helps to quickly adjust the segment by expanding and contracting the window without repeatedly examining the same characters.

The process starts by expanding the window one character at a time and using a hash map to record the frequency of each character within the window. It also tracks the count of the most frequent characters in the window to determine how many characters need to be replaced to make the window uniform. If the difference between the window size and this highest frequency exceeds the allowed number of replacements, the window is contracted from the start until it becomes valid again. Throughout this process, the maximum valid window size is continuously updated, and finally, the length of the longest valid substring is returned.

Here are the detailed steps of the algorithm that we have just discussed:

1. We start by initializing the data structures and variables required to track the sliding window clearly:

   1. lengthOfMaxSubstring will track the length of the longest valid substring found; this is initially set to 0.

   2. start pointer marks the left boundary of the sliding window; this is initially set to 0.

   3. We create a frequency map, charFreq, that keeps track of how many times each character appears within our current sliding window.

   4. A counter, mostFreqChar, tracks the maximum frequency of any character within our current window; this is initially set to 0.

2. Next, we iterate over the string using a pointer, end, starting from 0 to stringLength - 1:

   1. First, we take the character at the current position end.

   2. Then, we update the frequency count of this character in the charFreq map:

      1. If the character does not exist in charFreq, we initialize its frequency to 1.

      2. If the character is already present, we increment its frequency by 1.

   3. After updating this frequency, we compare the updated count of this character with the current mostFreqChar. If the new frequency is greater, we set mostFreqChar equal to this new higher frequency.

   4. After each character addition, we check if the current window is valid. Specifically, we check if the number of replacements needed (calculated as (end - start + 1) - mostFreqChar) exceeds k:

      1. If replacements exceed k, we reduce the window size by:

         1. Decreasing the character frequency at position start in the charFreq map by 1 because this character will no longer be inside our window.

         2. Moving the start pointer forward by one position, contracting the window to restore validity.

      2. Finally, we compare the length of our current window (end - start + 1) with lengthOfMaxSubstring. If the current window length is larger, we update lengthOfMaxSubstring to this new value.

3. Once the whole string has been traversed, we return the recorded value of lengthOfMaxSubstring, representing the length of the longest substring that can be converted into a uniform substring by replacing at most k characters.