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 lowercase English character.

Constraints:

• $1 \leq$ s.length $\leq 10^3$
• s consists of only lowercase 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

The naive approach would be iterating over each character of the string to form all possible substrings. For each character, we explore all possible substrings starting from that position. Within each substring, we calculate the number of required replacements to make all characters identical using a nested loop. If the count is less than or equal to k, and the length of the substring is longer than the previous longest identical character substring, we update the length. This approach utilizes three nested loops, resulting in a time complexity of $O(n^3)$, where n is the length of the input string.

Optimized approach using sliding window

The solution to this problem can be optimized using the sliding window pattern. For this purpose, we use two pointers to slide our window over the input string. We initialize the start and the end pointer with $0$. To move the window over the input string, we change the positions of the pointers as follows:

• Increment the end pointer until the window becomes invalid.
• Increment the start pointer only if the window is invalid to make it valid again.

We keep track of the frequency of characters in the current window using a hash map. We also maintain a variable, lengthOfMaxSubstring, to keep track of the longest substring with the same characters after replacements and mostFreqChar to keep track of the frequency of the most occurring character.

We check whether the new character is in the hash map in each iteration. If it is present in the hash map, we increment its frequency by $1$; otherwise, we add the character in the hash map and set its frequency to $1$. Next, we compare the frequency of the new character with mostFreqChar to update the frequency of the most occurring character so far using the following expression:

$$max(most \space freq \space char, \space frequency \space of \space new \space character)$$

Then, we use the following expression to check if the number of characters in the window other than the most occurring character is greater than k:

$$end \space - \space start \space + \space 1 \space - \space most \space freq \space char \space > \space k$$

If the expression above returns TRUE, the number of replacements required in the current window has exceeded our limit, that is, k. In this case, we decrement the frequency of the character to be dropped out of the window and adjust the window by moving the start pointer by $1$ to make the window valid again. We continue this process until we have traversed the entire string.

Then, we update lengthOfMaxSubstring with the current window size if the window size is greater than lengthOfMaxSubstring.

Finally, when the entire input string has been traversed, we return the length of the longest substring such that all the characters in the substring are the same.

The following illustration shows the algorithm explained above: