Leetcode 424 - Longest Repeating Character Replacement

Understanding the problem

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 substring that contains all repeating letters you can get after performing the above operations.

Plan your solution

One approach to solve this problem is to use a sliding window and a count of the most frequent letter in the current window. We can use a hashmap to keep track of the frequency of each letter in the current window.

We start by initializing a left and right pointer, and a count of the most frequent letter. We then move the right pointer to the right and update the hashmap with the new letter. If the new letter is the most frequent letter, we increment the count. If the new letter is not the most frequent letter, we decrement the count.

If the number of operations we have performed, represented by the size of the window minus the count of the most frequent letter, is greater than k, we move the left pointer to the right and update the hashmap accordingly.

We update the maximum length of the substring every time we move the right pointer.

Implement your solution

def characterReplacement(s: str, k: int) -> int:
    left = 0
    count = {}
    max_count = 0
    max_length = 0
    for right in range(len(s)):
        count[s[right]] = count.get(s[right], 0) + 1  #increment the count of current character
        max_count = max(max_count, count[s[right]])  #update the max count of any char seen so far
        if right - left + 1 - max_count > k:  
            count[s[left]] -= 1 #decrement the count of char at left pointer
            left += 1  #move left pointer to right
        max_length = max(max_length, right - left + 1) #update the max length of substring
    return max_length

Test your solution

Let’s test our solution with the example inputs:

s = "ABAB"
k = 2
print(characterReplacement(s, k))

Output: 4

As we can see, the output is correct and matches the expected output.

In summary, we have successfully implemented a solution to Leetcode Problem 424 by using a sliding window approach and keeping track of the frequency of each letter in the current window. We also kept track of the most frequent letter and the number of operations performed. We moved the left pointer and updated the hashmap accordingly if the number of operations performed was greater than k. Finally, we updated the maximum length of the substring every time we moved the right pointer. This approach has a time complexity of O(n) and a space complexity of O(1), where n is the size of the input string.

Related Posts

• Two Sum and Its Variants
• Leetcode 1004 - Max Consecutive Ones III
• Leetcode 222 - Count Complete Tree Nodes
• Leetcode 1027 - Longest Arithmetic Subsequence
• Question 1299 on leetcode
• Leetcode 240 - Search a 2D Matrix II
• Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
• Leetcode 239 - Sliding Window Maximum
• Leetcode 209 - Minimum Size Subarray Sum
• LeetCode 230 - Kth Smallest Element in a BST with Code
• advanced-applications-of-binary-search
• Leetcode 96 - Unique Binary Search Trees
• Leetcode 540 - Single Element in a Sorted Array
• Leetcode 1283 - Find the Smallest Divisor Given a Threshold
• Leetcode 74 - Search a 2D Matrix
• Leetcode 340 - Longest Substring with At Most K Distinct Characters
• Leetcode 300 - Longest Increasing Subsequence
• Leetcode 930 - Binary Subarrays With Sum
• Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
• Leetcode 704 - Binary Search
• Leetcode 643 - Maximum Average Subarray I
• LeetCode - Two Sum Solution with Code
• a-binary-search-template
• Leetcode 1358 - Number of Substrings Containing All Three Characters
• Leetcode 33 - Search in Rotated Sorted Array
• Leetcode 1151 - Minimum Swaps to Group All 1’s Together