Longest Repeating Character Replacement (C++, Java, Python)

There are a lot of programming problems related to strings of different difficulty levels. In this article, we will discuss the Longest Repeating Character Replacement problem from leetcode which falls under the concept of string manipulation. We will also implement it in C++, Java, and Python.

Longest Repeating Character Replacement

In this Longest Repeating Character Replacement problem, we are given a string and an integer we can choose any character of the string and change it to any other uppercase English character. We can perform this operation at most k times. We have to perform the above operation in such a way that we can get the length of the longest substring.

Let us discuss this better with an example:

Input: 
s = "AABABBA", k = 1

Output: 
4

Here we can replace A at index 3 with B to get four consecutive B or we can replace B at index 2 with A to get four consecutive A.

Solve using Sliding Window and HashMap

In this approach, we will use the concept of a sliding window in which we use sliding window to expand and contract while maintaining the count of characters within the window.

Below are the steps to be used in this approach:

First of all, we will declare an unordered map to keep track of the count of each character present in the given string.
Now we will initialize three variables “ans”, “left”, and “right”
- ans keeps track of the maximum length of the substring and left and right maintains window size.
Now we will iterate through our string using the right pointer and update our map with the frequency of characters. Simultaneously we will check if the length of the current substring minus the frequency of the most frequent character exceeds the allowed replacement “k”
If yes then we will move the left pointer to the right and decrease the count of the character at the left.
If not then we will update our ans with maximum window size.
At last, we will return our ans after we iterate our string.

C++ Code

Below is the solution for longest repeating character replacement:

#include <iostream>
#include <unordered_map>
#include <algorithm>

using namespace std;

int characterReplacement(const string& s, int k) {
    // Initialize an unordered_map to keep track of the count of each character
    unordered_map<char, int> alphabets;

    // Initialize variables for the answer and left pointer
    int ans = 0;
    int left = 0;

    // Iterate through the string using the right pointer
    for (int right = 0; right < s.length(); ++right) {
        // Update the count of the current character in the unordered_map
        alphabets[s[right]] = 1 + alphabets[s[right]];

        // Check if the current window size minus the count of the most frequent character
        // is greater than the allowed replacements (k)
        if ((right - left + 1) - max_element(alphabets.begin(), alphabets.end(),
            [](const auto& p1, const auto& p2) { return p1.second < p2.second; })->second > k) {
            // If so, move the left pointer and decrease the count of the character at the left
            alphabets[s[left]] -= 1;
            left += 1;
        } 
      	else {
            // Update the answer with the maximum window size
            ans = max(ans, (right - left + 1));
        }
    }

    // Return the final answer
    return ans;
}

int main() {
    string s = "AABABBA";
    int k = 1;

    int result = characterReplacement(s, k);

    cout << "Result: " << result << endl;

    return 0;
}

Python Code

Implement the solution for the longest repeating character replacement:

def character_replacement(s, k):
    # Initialize a dictionary to keep track of the count of each character
    alphabets = {}
    # Initialize variables for the answer and left pointer
    ans = 0
    left = 0

    # Iterate through the string using the right pointer
    for right in range(len(s)):
        # Update the count of the current character in the dictionary
        alphabets[s[right]] = 1 + alphabets.get(s[right], 0)

        # Check if the current window size minus the count of the most frequent character
        # is greater than the allowed replacements (k)
        if (right - left + 1) - max(alphabets.values()) > k:
            # If so, move the left pointer and decrease the count of the character at the left
            alphabets[s[left]] -= 1
            left += 1
        else:
            # Update the answer with the maximum window size
            ans = max(ans, (right - left + 1))

    return ans

# Example usage
s = "AABABBA"
k = 1
result = character_replacement(s, k)
print("Result:", result)

Java Code

Implement it in Java also:

import java.util.HashMap;
import java.util.Map;

public class CharacterReplacement {
    public static int characterReplacement(String s, int k) {
        // Initialize a map to keep track of the count of each character
        Map<Character, Integer> alphabets = new HashMap<>();
        // Initialize variables for the answer and left pointer
        int ans = 0;
        int left = 0;

        // Iterate through the string using the right pointer
        for (int right = 0; right < s.length(); ++right) {
            // Update the count of the current character in the map
            alphabets.put(s.charAt(right), 1 + alphabets.getOrDefault(s.charAt(right), 0));

            // Check if the current window size minus the count of the most frequent character
            // is greater than the allowed replacements (k)
            if ((right - left + 1) - alphabets.values().stream().max(Integer::compare).orElse(0) > k) {
                // If so, move the left pointer and decrease the count of the character at the left
                alphabets.put(s.charAt(left), alphabets.get(s.charAt(left)) - 1);
                left += 1;
            } 
          	else {
                // Update the answer with the maximum window size
                ans = Math.max(ans, (right - left + 1));
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        // Example usage
        String s = "AABABBA";
        int k = 1;
        int result = characterReplacement(s, k);
        System.out.println("Result: " + result);
    }
}

Output:

Result: 4

The Time Complexity to solve the longest repeating character replacement problem using sliding window and hashmap is O(N) where n is the length of the string because our left and right pointers traverse the string exactly once.

The Space Complexity is O(1) because the hashmap can have a maximum of 26 unique characters and the size of the hashmap will remain constant.

Conclusion

In conclusion, we found that the sliding window approach provides an efficient solution for the longest repeating character replacement leetcode problem with time complexity of O(N) and space complexity of O(1) we have also implemented code in C++, Java, and Python.