Solution: Longest Repeating Character Replacement

Let's solve the Longest Repeating Character Replacement problem using the Sliding Window pattern.

We'll cover the following

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≤1 \leq s.length ≤103\leq 10^3
  • s consists of only lowercase English characters
  • 0≤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(n3)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 00. 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 11; otherwise, we add the character in the hash map and set its frequency to 11. 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 freq char, frequency of new character)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 − start + 1 − most freq char > kend \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 11 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:

Let’s have a look at the code for the algorithm we just discussed.

import java.util.*;
public class RepeatingCharacter {
    public static int longestRepeatingCharacterReplacement(String s, int k) {
        int stringLength = s.length();
        int lengthOfMaxSubstring = 0;
        int start = 0;
        Map<Character, Integer> charFreq = new HashMap<>();
        int mostFreqChar = 0;
        for (int end = 0; end < stringLength; ++end) {
            char currentChar = s.charAt(end);
            
            charFreq.put(currentChar, charFreq.getOrDefault(currentChar, 0) + 1);
            
            mostFreqChar = Math.max(mostFreqChar, charFreq.get(currentChar));
            if (end - start + 1 - mostFreqChar > k) {
                charFreq.put(s.charAt(start), charFreq.get(s.charAt(start)) - 1);
                start += 1;
            }
            lengthOfMaxSubstring = Math.max(lengthOfMaxSubstring, end - start + 1);
        }
        return lengthOfMaxSubstring;
    }
    // Driver code
    public static void main(String[] args) {
        List<String> inputStrings = Arrays.asList("aabccbb", "abbcb", "abccde", "abbcab", "bbbbbbbbb");
        List<Integer> k = Arrays.asList(2, 1, 1, 2, 4);
        for (int i = 0; i < inputStrings.size(); ++i) {
            System.out.println((i + 1) + ".\tInput String: '" + inputStrings.get(i) + "'");
            System.out.println("\tk: " + k.get(i));
            System.out.println("\tLength of the longest substring with repeating characters: "
                    + longestRepeatingCharacterReplacement(inputStrings.get(i), k.get(i)));
            System.out.println(new String(new char[100]).replace("\0", "-"));
        }
    }
}
Longest Repeating Character Replacement

Solution summary

To recap, the solution can be divided into the following parts:

  1. We iterate over the input string using two pointers.

  2. In each iteration:

    1. If the new character is not present in the hash map, we add it. Otherwise, we increment its frequency by 1.
    2. We slide the window one step forward if the number of replacements required in the current window has exceeded our limit.
    3. If the current window is the longest so far, then we update the length of the longest substring that has the same character.

  3. Finally, we return the length of the longest substring with the same character after replacements.

Time complexity

The time complexity of the solution is O(n)O(n), where nn is the length of the input string because we iterate over the input string only once.

Space complexity

The space complexity of the solution is O(1)O(1), since we will be storing the frequency of 2626 characters at most in the hash map.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.