Longest Repeating Character Replacement - Leetcode 424 - Sliding Window (Python)

Please check my playlists for free DSA problem solutions:

Best Courses for Analytics:
---------------------------------------------------------------------------------------------------------

Best Courses for Programming:
---------------------------------------------------------------------------------------------------------

Best Courses for Machine Learning:
---------------------------------------------------------------------------------------------------------

Best Courses for Statistics:
---------------------------------------------------------------------------------------------------------

Best Courses for Big Data:
---------------------------------------------------------------------------------------------------------

More Courses:
---------------------------------------------------------------------------------------------------------

Full Disclosure:
Please note that I may earn a commission for purchases made at the above sites! I strongly believe in the material provided; I only recommend what I truly think is great. If you do choose to make purchases through these links; thank you for supporting the channel, it helps me make more free content like this!

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[KrishnaSingh-rdpr]

you are the first non indian creator whom i have reffered to for a leetcode

[Moses-ffpr]

Man. This is brilliant. I found it better than neetcode 🎉

[JoeTan-nqfq]

To find max of count in every iteration tends to slow thing down since each time it is O(n). Using hashmap will reduce to O(1) for this operation.
In each iteration,
hashmap[s[r]] = hashmap.get(s[r], 0) + 1
max_freq = max(max_freq, hashmap[s[r]])

# Shrink window until k is not exceeded
if (r - l + 1) - max_freq > k:
hashmap[s[l]] -= 1
l += 1

# Store max_len
max_len = max(max_len, r - l + 1)

[ssuriset]

This. Is the craziest shit I have ever seen, and the way you explained it - you’re awesome.

[christianjt]

Nice! that trick to check if the string is valid was very creative.

[myname]

We dont need an array of 26 zeroes. We can just have a hashmap whose key which would be the letter and value which would be the no of times that specific letter occured. Then take a max() of the values. Not very much of an optimisation but just a thought. Awesome explanation!

[arzijeziberovska]

You are really great at explaining so one understands! Please keep up!! 🙌🙌🙌

[Saisam]

You could use the ord("A") instead of the arbitrary value 65. Also you don't really need a while loop. I agree with others that using a dictionary here is probably more readable and easier to understand, while maintaining the same Space.

[nguyenkhiem]

Awesome explanation and solution. Super insightful, kudos to you Greg

[devanshsharma]

great explanation! I really liked this solution too.

[jz]

I couldn't figure out the solution a 2nd time, after coming back deep, from Neetcode's roadmap lol. I just couldn't recognize what type of problem this was. I guess I'll come back again a 3rd time to see if I remember... After 200 more problems lol.

[asthajain]

Could you explain the while loop condition I think it is used to check invalid window but could you explain it a lil further?

[amitn]

I understand the logic behind the algorithm.However there is a part that i am missing, what about the use of k?
Don’t we need to add the action of the choice to swap characters?

[omkarsawant]

We can refine the code for clarity and efficiency without changing its time complexity. Below are some improvements:

1)Use a defaultdict from the collections module for cleaner code. Use is it initializes a dictionary that returns 0 for missing keys by default, simplifying the code for updating character counts.
2)Maintain the maximum frequency of any character in the current window. This avoids recalculating the maximum frequency within the sliding window repeatedly, thus improving efficiency.

Code Snippet with comments Below with Test Example:

from collections import defaultdict

class Solution:
def characterReplacement(self, s: str, k: int) -> int:
# Initialize the left pointer of the sliding window
l = 0

# Dictionary to count the frequency of characters in the current window
counts = defaultdict(int)

# Variable to keep track of the highest frequency of any single character in the current window
max_freq = 0

# Variable to keep track of the length of the longest valid substring found so far
longest = 0

# Iterate over the string with the right pointer of the sliding window
for r in range(len(s)):
# Increment the count of the current character in the window
counts[s[r]] += 1

# Update the maximum frequency of any character in the current window
max_freq = max(max_freq, counts[s[r]])

# Check if the current window is valid
if (r - l + 1) - max_freq > k:
# If the window is not valid, decrement the count of the character at the left pointer
counts[s[l]] -= 1

# Move the left pointer to the right to shrink the window
l += 1

# Update the length of the longest valid substring
longest = max(longest, r - l + 1)

# Return the length of the longest valid substring found
return longest

def main():
# Create an instance of the Solution class
solution = Solution()

# Test case 1
s1 = "ABAB"
k1 = 2
print(f"Test case 1: s = {s1}, k = {k1} -> Output: {solution.characterReplacement(s1, k1)}")

# Test case 2
s2 = "AABABBA"
k2 = 1
print(f"Test case 2: s = {s2}, k = {k2} -> Output: {solution.characterReplacement(s2, k2)}")

# Ensure that the main function is called only when the script is executed directly
if _name_ == "__main__":
main()

[Xjdjdhdh-trjq]

I dont know in python if the max[] method can update the max value every time in the while loop, but at least in java, the value isnt updated in every while loop.
Turns out it still pass all the test, but still confuse me why it still works....

[georgesneaimeh]

Does it work for the string : AABBCBBABAACCCA ??
Because max appearances is A but if we work it on B it is better so we have to account in the max value the case where max of second best option.
In other words if the difference between the first max letter and the second less or equal to k, then we do the job on both letters and we see which one is the longest streak of letters.

[VitaliyBorisok]

It looks like in Java implementation in GitHub you never recalculate maxCount when shrinking window because of `(r - l + 1) - maxCount > k`. Do I miss something?

[Moses-ffpr]

Kindly zoom in while you are writing the code

[eduardofigueiredo]

You could also binary search for the answer