Problem Description

Longest Repeating Character Replacement, Given a string s that consists of only uppercase English letters, you can perform at most k operations on that string. In one operation, you can choose any character of the string and change it to any other uppercase English character. Find the length of the longest sub-string containing all repeating letters you can get after performing the above operations.

Solution

To solve this problem, we will use a sliding window approach. We will consider a window of characters and try to expand it as much as possible. We will keep track of the count of the characters in the window and the maximum count of any character in the window. We will then check if we can make all characters in the window the same by replacing some characters. If we can, we will expand the window. If we can't, we will shrink the window.

Here is the step-by-step code solution:

def characterReplacement(s: str, k: int) -> int:
    n = len(s)
    count = [0] * 26
    max_count = 0
    start = 0
    res = 0
    for end in range(n):
        count[ord(s[end]) - ord('A')] += 1
        max_count = max(max_count, count[ord(s[end]) - ord('A')])
        while end - start + 1 - max_count > k:
            count[ord(s[start]) - ord('A')] -= 1
            start += 1
        res = max(res, end - start + 1)
    return res

In the above code, we first initialize an array called count to keep track of the count of each character in the window. We also initialize max_count to 0, which will keep track of the maximum count of any character in the window. We set start to 0, which is the starting index of the window. We also initialize res to 0, which will keep track of the length of the longest sub-string containing all repeating letters.

We then loop through the string s using a variable end. We increment the count of the character at index end in the count array. We update max_count to be the maximum count of any character in the window.

We then check if we can make all characters in the window the same by replacing some characters. We do this by checking if the length of the window (end - start + 1) minus the maximum count of any character in the window is greater than k. If it is, we need to shrink the window. We do this by decrementing the count of the character at index start in the count array and incrementing start.

We then update res to be the maximum of its current value and the length of the current window (end - start + 1).

Finally, we return res, which is the length of the longest sub-string containing all repeating letters.

Complexity Analysis

The time complexity of this solution is O(n), where n is the length of the string s. This is because we loop through the string once and do constant time operations in each iteration.

The space complexity of this solution is O(1), because we use a constant amount of extra space to store the count array, max_count, start, and res.

Conclusion

In this blog post, we have learned how to solve the Longest Repeating Character Replacement problem using a sliding window approach. We have explained the problem, provided a step by step solution, analyzed its time and space complexity, and concluded with some cheerful words. Happy Coding!😎