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)
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!
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.
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?
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.
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....
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.
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()
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?
As far, as I understand, for final result any case when maxCount was the real max - is the best solution. Any decreased (maxCount + k) will always be less than (overallMaxCount + k), so it doesn't affect final result. As a conclusion: python code can be improved the same way: you can calculate max on line 8 on flight and don't do max(counts) on line 9. Time complexity stays the same, but real speed is better.
Master Data Structures & Algorithms For FREE at AlgoMap.io!
you are the first non indian creator whom i have reffered to for a leetcode
Man. This is brilliant. I found it better than neetcode 🎉
This. Is the craziest shit I have ever seen, and the way you explained it - you’re awesome.
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)
Nice! that trick to check if the string is valid was very creative.
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!
You are really great at explaining so one understands! Please keep up!! 🙌🙌🙌
Thank you! Glad to hear it :)
Awesome explanation and solution. Super insightful, kudos to you Greg
Sorry for the slow response! Thank you very much :)
goddam this is better than Neetcode
Happy to hear it's helpful!
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.
Loving this content
great explanation! I really liked this solution too.
Could you explain the while loop condition I think it is used to check invalid window but could you explain it a lil further?
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?
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.
This one is definitely a bit tricky yeah
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....
I liked your solution yoohoo!
Awesome, yoohoo!
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.
The solution provided will work for all strings
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()
I just implemented this idea, the code is easier to understand now. Thanks for the suggestion!
Kindly zoom in while you are writing the code
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?
As far, as I understand, for final result any case when maxCount was the real max - is the best solution. Any decreased (maxCount + k) will always be less than (overallMaxCount + k), so it doesn't affect final result.
As a conclusion: python code can be improved the same way: you can calculate max on line 8 on flight and don't do max(counts) on line 9. Time complexity stays the same, but real speed is better.
You could also binary search for the answer
how? you would need to sort the window. Also how would you find the longest length?
hey gregg. why didn't you just use dictionary, like a sane person? just genuinely curious lol. also, great list btw, i have so far finished 43/100!