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.