Longest Repeating Character Replacement Leetcode 424 [Python]

In this blog post, we will tackle the Longest Repeating Character Replacement problem from LeetCode, a platform known for its algorithmic challenges.

We'll break down the problem, provide both a brute-force and an efficient solution, discuss the reasoning behind our approach, and examine the time and space complexity of our code.

Problem Overview

Problem Name: Longest Repeating Character Replacement
Difficulty: Medium
Category: Sliding Window
Companies: Google

Question:
You are given a string s and an integer k.

You can choose any character of the string and change it to any other uppercase English character.

You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".

The substring "BBBB" has the longest repeating letters, which is 4. There may exist other ways to achieve this answer too.

Constraints:
– 1 <= s.length <= 105
– s consists of only uppercase English letters.
– 0 <= k <= s.length

Understanding Constraints

Before we dive into the solution, it's crucial to understand the constraints given in the problem.

The input string s can have a maximum length of 105 characters.

This implies that our solution should be efficient enough to handle inputs of this size within a reasonable time frame.

Additionally, s contains only uppercase English letters, which means we don't have to consider lower-case letters or special characters.

The value of k represents the maximum number of character replacements allowed.

This is a crucial constraint as it dictates how flexible our solution needs to be.

If k is low, it may not be possible to change many characters, while a higher k allows more flexibility.

Our solution should adapt to this value.

Longest Repeating Character Replacement LeetCode Problem Solution

Let's proceed to discuss the solution to this problem.

We will provide two solutions: a brute-force approach and an efficient approach.

1. Bruteforce Approach

The brute-force approach is a straightforward way to solve the problem, but it's not the most efficient one.

The idea is to consider every possible substring in the given string and check if it can be converted into a substring with the same character.

To do this, we'll iterate through the string and, for each character, explore the substrings by making at most k replacements.

We'll keep track of the maximum valid substring length we find.

def characterReplacement(self, s: str, k: int) -> int:
    n = len(s)
    max_length = 0

    for i in range(n):
        for j in range(i, n):
            substring = s[i:j+1]
            max_char = max(set(substring), key=substring.count)
            
            replacements_needed = len(substring) - substring.count(max_char)
            
            if replacements_needed <= k:
                max_length = max(max_length, len(substring))

    return max_length

This approach will work, but it has a time complexity of O(n^3), where n is the length of the input string.

The reason for this is that for each character in the string, we may need to consider all possible substrings.

This is highly inefficient and won't work well for large inputs.

2. Efficient Approach with Sliding Window

To optimize the solution, we can use a sliding window technique.

The main idea is to maintain a window that contains the most frequent character in the current substring while keeping track of the maximum valid substring length.

We'll adjust the window size by moving both the left and right pointers.

Let's break down the efficient approach into the following steps:

1. Initialize a dictionary (or array) to store the count of each character in the current window.
2. Maintain a left pointer (initially at the beginning of the string) and a right pointer (which will traverse the string).
3. While moving the right pointer, update the character count in the window.
4. Check if the window is valid, i.e., the number of replacements needed is less than or equal to k.

If not, increment the left pointer to shrink the window.
5. Update the result with the maximum valid window length.

Let's implement this solution in Python:

def characterReplacement(self, s: str, k: int) -> int:
    # Initialize variables
    counts = {}  # Dictionary to store character counts in the current window
    max_length = 0  # Maximum valid substring length
    left = 0  # Left pointer

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

        # Find the maximum character count in the current window
        max_count = max(counts.values())

        # Check if the window is valid (replacements needed <= k)
        if (right - left + 1) - max_count > k:
            # The window is not valid, so increment the left pointer
            counts[s[left]] -= 1
            left += 1

        # Update the maximum valid substring length
        max_length = max(max_length, right - left + 1)

    return max_length

This optimized solution has a time complexity of O(n) since we iterate through the string only once.

It efficiently maintains the sliding window and updates the result.

This approach is highly efficient and can handle inputs with the maximum constraints specified in the problem.

Time and Space Complexity

Let's analyze the time and space complexity of our efficient solution:

• Time Complexity: Our algorithm traverses the input string once, so it has a time complexity of O(n), where n is the length of the string.

• Space Complexity: We use a dictionary (counts) to store character counts in the current window.

In the worst case, this dictionary can contain all 26 uppercase English characters.

Therefore, the space complexity is O(26), which simplifies to O(1), as it's a constant space.

Our efficient approach is both time and space-efficient, making it a suitable solution for large inputs.

Reasoning Behind Our Approach

The key to solving this problem efficiently lies in maintaining a sliding window and continuously checking the validity of the window based on the constraints.

By keeping track of the most frequent character in the window and making necessary adjustments when the window is not valid, we can achieve an optimal solution.

We do not need to consider all possible substrings, which would lead to an impractical time complexity.

Instead, we dynamically adjust the window size to ensure that the maximum valid substring length is obtained.

Related Interview Questions By Company:

• Combinations LeetCode
• Word Break LeetCode
• Partition List LeetCode

Related Interview Questions By Difficulty:

• Minimum Window Substring LeetCode
• Contains Duplicate II LeetCode
• Longest Substring Without Repeating Characters LeetCode

Related Interview Questions By Category:

• Reconstruct Itinerary LeetCode
• Number Of Connected Components In An Undirected Graph LeetCode
• Invert Binary Tree LeetCode

Conclusion

In this blog post, we tackled the "Longest Repeating

Character Replacement" problem from LeetCode.

We discussed the problem statement, provided both a brute-force and an efficient solution, and explained the reasoning behind our efficient approach.

The efficient approach, based on the sliding window technique, is the recommended solution as it has a time complexity of O(n) and handles the constraints specified in the problem.

By maintaining a window and adjusting it based on character counts, we efficiently find the longest substring containing the same character after making at most k replacements.

This solution is both elegant and performant, making it suitable for a wide range of inputs.

If you have any questions or suggestions, please feel free to ask.

Happy coding!