Permutation in String - Leetcode 567 - Python
Vložit
- čas přidán 26. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: neetcode.io/problems/permutat...
0:00 - Read the problem
4:10 - Drawing Explanation
11:42 - Coding Explanation
leetcode 567
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#microsoft #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Just a personal opinion, I think it would have been easier to understand if you had explained the O(26*n) in code and what needs to be changed there for O(n) as an optimization.
Agreed. I think the O(26*n) solution is just sliding the window as it is in the o(n) which is size of s1. For every window you check for every char count in s1 is at least equal to char count in s2 of the current window. If not slide the window as it is now
Note: You need to shift the window since it’s possible the char count matches but it isn’t a consecutive permutation. Same as the optimized solution here. In other words you can’t just move the right pointer by 1 until end of string.
I tried the 0(26*n) but it's showing error for me
But needcode's this solution is just a example pattern to solve others. And actually, this pattern is usually used to solve other problems. So I think we should learn about it for the further using.
NC tries to make his video ~20 mins and the optimized solution is reasonably well-explained considering its length. You can def find solution O(26n) on discussion tho.
exactly
First Neetcode vid I didn't really like,
too much boilerplate and setup. Why not just use a hashmap?
I agree. But considering the number of video solutions he has created, I will 100% excuse this and still believe him to be the GOAT of leetcode
Even better solution is make a map of letters in smaller string with count of letter. And with sliding window iterate and check if character in map. If not Shift window to one next to the mismatch. If all match add 1 to answer. And move sliding window by 1 and keep checking if the new addition there in map until we find a mismatch. In which case we will move window to one next to mismatch
yes indeed, I had the same intuition.
This solution does not account for multiple occurrences of the same character in s1. If a mismatch occurrs in the frequency of some character 'a', then we should move the start pointer so as to exclude the first occurrence of 'a' rather than moving it to the current index + 1.
There is a way that you only need one hashmap. Initialize the hashmap with all chars in s1 count = 1, reduces to min window substring type of problem.
Nice solution, but this solution is an over kill. Using 2 hashmaps should be fine in interviews. Probably if you're asked to optimize, then you can try this solution.
My solution btw:
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
s1_map = Counter(s1)
s2_map = Counter()
if len(s1) > len(s2):
return False
for i in range(len(s2)):
s2_map[s2[i]] += 1
if i >= len(s1):
if s2_map[s2[i - len(s1)]] > 1:
s2_map[s2[i - len(s1)]] -= 1
else:
del s2_map[s2[i - len(s1)]]
if s1_map == s2_map:
return True
return False
@@mbdev How do you figure? O(26n) eq to O(n)
@@MrFantasticMunch (removed my initial comment). thanks. i stand corrected here. O(26) can be considered constant.
beautiful solution
Wouldn't this be O(len(s1) * len(s2))?
@@LuisRoel don’t remember the video but n is probably the size of both strings
Great video - I found that completing Valid Anagrams question using an array (instead of a hashmap) helped with my understanding of this solution.
You make leetcode questions interesting!
i think this solution is very confusing
I never thought I would enjoy solving problems. The way you explain these solutions are invigorating!
Indeed.
Thank you so much for all the great videos. Here is another I did without comparing the whole hashmap:
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
length = len(s1)
left = 0
s1_dict = {}
for c in s1:
s1_dict[c] = 1 + s1_dict.get(c, 0)
s2_dict = {}
for right in range(len(s2)):
if s2[right] not in s1_dict:
s2_dict.clear()
left = right + 1
continue
s2_dict[s2[right]] = 1 + s2_dict.get(s2[right], 0)
while s2_dict[s2[right]] > s1_dict[s2[right]]:
s2_dict[s2[left]] -= 1
left += 1
if (right - left == length - 1) \
and (s2_dict[s2[right]] == s1_dict[s2[right]]):
return True
return False
ugly monstrosity
hands down best algo tutorials on the internet right now!
Phew, that's a bit of code! I prefer a simpler approach with a single hashmap of only the letters in S1.
Algorithm:
1. Build a frequency dictionary of all characters in S1.
2. Initialize a left pointer to 0.
3. Your right pointer for the sliding window will be part of the [for] loop that iterates over S2. Start the for loop.
If you encounter a character that's in your S1_freq_dict, decrement the frequency.
If the character's new frequency is 0 and the current window size is equivalent to the length of S1, return TRUE!
If the character's new frequency is less than 0, enter a while loop until the frequency is reset to 0:
In the while loop, increment the frequency of the character at the left pointer, then increment the left pointer.
ELSE (character is not in S1_freq_dict)
Update left pointer to right pointer + 1 (i + 1)
Reset S1_freq_dict to a fresh copy of the original dict.
Code:
def checkInclusion(self, s1: str, s2: str) -> bool:
freq = {}
for c in s1:
freq[c] = freq.get(c, 0) + 1
freq_copy = freq.copy()
l = 0
for i in range(len(s2)):
if s2[i] in freq:
freq[s2[i]] -= 1
if freq[s2[i]] == 0 and i - l + 1 == len(s1):
return True
while freq[s2[i]] < 0:
freq[s2[l]] += 1
l += 1
else:
freq = freq_copy.copy()
l = i + 1
return False
Underrated. I was also thinking along these lines but was failing to update hashmap properly for else condition. I did not attempt to use copy function. I was trying to increment "start"/"left" pointer one by one while incrementing the corresponding character in hashmap but it was failing because of some catch 21 situation. Fixing one thing broke xyz testcases and fixing code for xyz cases broke abc testcases... copy() was neat as that worked for all cases.
Awesome code. Although this algo in Java is little bit slower than Leetcode official solution. Here is the Java conversion:
public boolean checkInclusion(String s1, String s2) {
HashMap map = new HashMap();
for (int i = 0; i < s1.length(); i++) {
map.put(s1.charAt(i), map.getOrDefault(s1.charAt(i),0)+1);
}
int left=0;
HashMap temp = new HashMap();
temp.putAll(map);
for(int i=0; i
Interesting solution.
Looks like the dict.copy() is O(m*n) in the worst case.
"if s2[i] in freq" statement will take O(n) time to execute ... so overall TC of your algo will be O(n^2) ... Please correct me if I am wrong
@@sagarverma868 `freq` is a dictionary, so look-up for `if s2[i] in freq` will be O(1).
the straight forward sliding window :
my solution :
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1)>len(s2) : return False
window=len(s1)
sequence1 = sorted(s1)
l=0
r=window-1
while r < len(s2):
sequence=s2[l:r+1]
if sorted(sequence)==sequence1 : return True
l+=1
r+=1
return False
this is nlogn since you are using the sorted function within the while loop
I managed to figure this out on my own! I think I'm getting better at solving these sorts of problems with your help.
Solved it in 10 minutes days after watching all your videos about sliding windows. It's hard to express what I feel!
You are a genius. I saw this video, solved 576 and went on to solve 1004. Thanks a lot!
Wow! This is super smart.
Also, Thanks a lot for taking the time and effort to explain things in such an understandable way! Really appreciate it
This was a lot of boiler plate code for a sliding window solution.
No matter what actual percentages are displayed after execution at the leetcode, the algorithm is always "pretty efficient")
making it O(26*n) -> O(n) made it way too complex
A simpler solution with amortised O(n) complexity
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
m_1=Counter(s1)
m_2=Counter(s2[:len(s1)])
if m_1==m_2:
return True
l=0
for i in range(len(s1),len(s2)):
m_2[s2[i]]+=1
m_2[s2[l]]-=1
if m_1==m_2:
return True
l+=1
return False
Thanks for the great video! Where can I find another relevant video of yours that gives a solution that uses hash map with sliding window, instead of arrays?
I found this method more intuitive where you only update s2_freq count if new and old char are different. First decrement matches, then update s2_freq array, then increment matches.
class Solution {
public:
bool checkInclusion(string s1, string s2) {
array s1_freq = {}, s2_freq = {};
int n1 = s1.length(), n2=s2.length(), matches=0;
if (n2 < n1) return false;
for (int i=0; i
Here's a somewhat simpler solution that I found:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
count1 = {}
count2 = {}
# Populate char counts of s1
for char in s1:
count1[char] = count1.get(char, 0) + 1
l = 0
for r in range(len(s2)):
count2[s2[r]] = count2.get(s2[r], 0) + 1
if (r - l + 1) > len(s1):
if count2[s2[l]] == 1:
del count2[s2[l]]
else:
count2[s2[l]] -= 1
l += 1
if count1 == count2:
return True
return False
Your explanations are always best!!
Hi Mr.Neet, you have about covered most graph topic but one that seems to be missing is strongly connected components. Would really appreciate it if you could teach that when you have time.
Mr neet loooool. Call him sir ya donkey
Hi Neetcode, thanks for this video. Can you also add 698. Partition to K Equal Sum Subsets
to the queue? This is marked as a medium but the official solution is super confusing. Also, there's no good python video solutions anywhere so it could really help the community
I hope this explanation helps someone who found this problem tricky -
If two strings are of same length, how can be determine if one is a permutation of the other?
One way is to check the frequencies of all the chars in s1 and s2. If they are exactly the same, that means they are permutations of each other. How many matches are needed? That will be equal to the number of characters allowed. In this case, the problem mentions that all are lowercase, so we need 26 matches.
We start by initializing the freq of first n characters of s1. We do this for s2 as well (for its n characters only). If the freq of all 26 chars match at this point, we can simply return true.
Otherwise, we will use sliding window to look for other substrings. We shift the window by 1 step. The freq of new char on right will increase. The freq of left most char in the previous window will decrease. Then, we can again check if the freq of all the 26 chars is exactly the same. If yes, they must be permutations of each other. So, return true.
```java
class Solution {
public boolean checkInclusion(String s1, String s2) {
int n = s1.length();
int m = s2.length();
if(n > m)
return false;
int[] f1 = new int[26];
int[] f2 = new int[26];
for(int i=0; i
if you are going to use extra memory anyways why not a hashmap class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
count=Counter(s1)
l,r=0,len(s1)-1
curr=Counter(s2[l:r+1])
while r
Isn’t the solution you proposed overkill until you’re asked to optimize? And isn’t this method more like to have more mistakes?
man who can think of that lol
This is some crazy stuff!
This solution will use some more memory, since it uses dictionaries:
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
start = 0
end = len(s1) - 1
s1_dict = {}
s2_dict = {}
if len(s2) < len(s1):
return False
else:
for i in s1:
if i in s1_dict:
s1_dict[i] += 1
else:
s1_dict[i] = 1
for i in range(len(s1)):
if s2[i] in s2_dict:
s2_dict[s2[i]] += 1
else:
s2_dict[s2[i]] = 1
while end < len(s2):
if s1_dict == s2_dict:
return True
break
end+=1
if end < len(s2):
if s2[end] in s2_dict:
s2_dict[s2[end]] += 1
else:
s2_dict[s2[end]] = 1
if s2[start] in s2_dict:
s2_dict[s2[start]] -= 1
if s2_dict[s2[start]] == 0:
del s2_dict[s2[start]]
start+=1
return not s1_dict != s2_dict
Still O(len(s2)) time, but dictionaries are slower than array-based solutions.
Here it is an algorithm using a similar approach but simpler, using only one hashmap of distinct s1 characters to store all occurrences and a set to use as flags for whether a match is pending or not:
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
dic = {}
pending = set()
for char in s1:
pending.add(char)
dic[char] = dic.get(char, 0) + 1
start = 0
for i, char in enumerate(s2):
if char in dic:
dic[char] -= 1
if dic[char] == 0:
pending.remove(char)
if len(pending) == 0:
return True
if i + 1 - start == len(s1):
firstChar = s2[start]
start += 1
if firstChar in dic:
dic[firstChar] += 1
if dic[firstChar] > 0:
pending.add(firstChar)
return False
leetcode made it so easy while implementing this solution. But when we implement the solution by ourselves, its not that easy ngl.
Clean approach:
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
counter1 = collections.Counter(s1)
counter2 = collections.Counter(s2[:len(s1)])
l = 0
for r in range(len(s1), len(s2)):
if counter1 == counter2:
return True
counter2[s2[l]] -= 1
counter2[s2[r]] += 1
l += 1
return counter1 == counter2
This approach would be O(26*n) for anyone wondering
I wonder if the regular sliding window solution is enough for interviews, this optimized one is quiet a bit trickier
Code wise, I think they both are similar - you use two hashmaps, and you have some of the similar structure in the code.
Finally I implemented a solution that imo, is better then yours. It feeling good notwithstanding, probably the first and last time it will happen.
I didn't understand shit, watched the video 5 times now! The comment section makes me look like the only dumb living person. :(
Easiest to understand : Just The Template
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2) :
return False
c = Counter(s1)
i,j = 0,0
while j < len(s2) :
if j - i + 1 == len(s1) :
f = Counter(s2[i:j + 1])
if c == f :
return True
i += 1
j += 1
return False
This problem and explanation is kind of stupefying... I still don't get it. Seems like a ton of work to keep track of matches of things you don't care to keep track of
Agree it's definitely complex. If it helps there's another problem that uses the same exact technique: czcams.com/video/jSto0O4AJbM/video.html
O(n)
2 hashmaps,
first stores freq of first string,
second stores freq as you iterate
matches when count in 1st == count in 2nd
if you remove so count no longer matches you decrease matches
if ever matches == size of first hashmap you found your solution
If is O(n) instead of O(26 + n) and it is easier to understand.
Maybe neetcode explains this solution as it helps with other problems? Not sure.
well, about comparing if two hashmaps are equal python does it for you in o(1) time if the size of them are different just do hashmap1 == hashmap2, but it's pretty clever that there's a way do do it without hashmap, and it can be faster in edge cases
Hey, what hardware/software do you use to draw your solutions?
I just use a computer, mouse and Paint3D.
Bro, unga way of explaining is in another level👌, antha parotta soori comedy ah ithula connect pananga patangala. Ur video peaked at that point🤣🤣
l=0
r=len(s1)
counter_s1=Counter(s1)
while(r
1) You don't need to specify an else, just let l+=1 and r+=1 outside an else.
2) You ignored that len(s1) could be greater than len(s2). Fail.
Please correct me If I am wrong !
Before removing the character from the window , We have to check if your current matches equals 26 and return there , before proceeding to remove the character and updating the matches ?
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
def arePermutations(s1, s2):
return Counter(s1) == Counter(s2)
L = 0
R = 0
while R < len(s2):
if R - L + 1 == len(s1):
sub_str = s2[L : R + 1]
if arePermutations(s1, sub_str):
return True
L = L + 1
R = L + 1
else:
R = R + 1
return False
i really am stupid
it can be easier to set match as len of target
This is extremely detail and easy to follow. Thank you for a great video!
Neetcode mentioned in the beginning that the technique used for the optimized O(n) approach is useful for other problems. Which are the other types of problems where this pattern is useful?
Hmm cant you initialize the matches value to the lenght of s1 since the first for loop will always increment by 1 the same index/char of both the lists? 🤔
Genius! You have made a medium question become easy :)
thank u man
Somewhat similar to today's Leetcode problem 438 - Find All Anagrams in a String
I believe the optimization is from O(26.n) to O(2.n), instead of to O(n), because we went from checking all counts of 26 letters in each loop, to checking counts of 2 letters (the character leaving the window and the character being added to the window) in each loop.
True
The question said the length of s1 will be less than or equal to 1 so that caused some confusion
Does the solution apply to if s1 contains duplicated characters? By changing 26 to 26+x where x is the extra numbers of duplicated c?
There are not enough C++ solutions in this comment section, therefore here I present mine which uses one hashmap and it takes O(n) time, (or better said O(2n)) instead of two hashmaps O(26n) approach. Hope it helps
class Solution {
public:
bool checkInclusion(string s1, string s2) {
unordered_map ump; //hashmap to store the elements of the string whose permutation is to be checked
for(char i : s1){
ump[i]++;
}
//if count becomes 0 which means that all letters exist in the other string, we return true
int left = 0; //left boundary of sliding window
int right = 0; //right boundary of sliding window
int count = ump.size(); // number of unique letters in s1
int windowlen = s1.length();
while(right
O(n) 128 ms:
- right pointer (variable R) goes from 0 to the last letter
- for each new letter I've used auxiliar structures to not fall on O(m) (m is s1 length).
- I've used 2 sets, one for s1 letters and other to keep CURRENT letters on WINDOW that has the same counting as s1. That means if you change the window so you have to change that set if needed.
class Solution {
func checkInclusion(_ s1: String, _ s2: String) -> Bool {
let windowLength = s1.count
let s2Length = s2.count
let s2Array = Array(s2)
let targetLettersSet = Set(s1)
var currentEqualLettersonWindow = Set()
var windowStringHashMap = [Character:Int]()
let targetSubStringHashMap = s1.reduce(into: [Character:Int]()) { map, character in
map[character, default: 0] += 1
}
var l = 0
var r = 0
while(r = windowLength {
let deletedLetter = s2Array[l]
windowStringHashMap[deletedLetter, default: 0] -= 1
// since you've removed a letter that is on target
if s1.contains(deletedLetter) {
// you deleted and after that you have the letter's amount you desire (or not) for the window
/// example: "adc", "dcda" -> you deleted D and it goes from 2 to 1
if windowStringHashMap[deletedLetter] == targetSubStringHashMap[deletedLetter] {
currentEqualLettersonWindow.insert(deletedLetter)
} else {
currentEqualLettersonWindow.remove(deletedLetter)
}
}
l += 1
}
// you've added a letter that is on target
if s1.contains(currentLetter) {
// you added and after that you have the letter's amount you desire (or not) for the window
if windowStringHashMap[currentLetter] == targetSubStringHashMap[currentLetter] {
currentEqualLettersonWindow.insert(currentLetter)
} else {
currentEqualLettersonWindow.remove(currentLetter)
}
}
if targetLettersSet.count == currentEqualLettersonWindow.count {
return true
}
r += 1
}
return false
}
}
I think this one is an even better approach :-
class Solution {
public:
bool checkInclusion(string s1, string s2) {
unordered_map check;
unordered_map record;
int l, r;
l=0;
r=0;
for (int i = 0; i < s1.length(); i++)
{
check[s1[i]]++;
}
if (s1.length() > s2.length())
{
return false;
}
else{
while(rcheck[s2[r]]){
while(l
Straightforward Python Anagram solution (w Hashmap):
class Solution(object):
def checkInclusion(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
# if s1 is longer than s2, return False as s2 can never contain s1 as a substring
if len(s1) > len(s2):
return False
# matched alphabets takes note of how many alphabets are matched in frequency for s1 and s2(sliding_window)
# s1_freq_map contains frequency of alphabets in s1, hence if s2(sliding_window) is able to negate the count of all alphabets to 0, s2 is able to contain the substr s1
matched_alphabets = 0
s1_freq_map = {}
for ch in s1:
if ch not in s1_freq_map:
s1_freq_map[ch] = 0
s1_freq_map[ch] += 1
start_idx = 0
for end_idx in range(len(s2)):
current_ch = s2[end_idx]
# decrement frequency if current_ch in s2 exists in s1_freq_map
if current_ch in s1_freq_map:
s1_freq_map[current_ch] -= 1
# if current_ch in s2 matches the corresponding freq in s1, the counter will be 0
# to take note of the match condition, we increase matched_alphabets by 1
if s1_freq_map[current_ch] == 0:
matched_alphabets += 1
# ensure that current window can not be longer than s1
while (end_idx - start_idx + 1) > len(s1):
starting_ch = s2[start_idx]
# remove starting_ch at start_idx, and increase back frequency count
# if frequency of starting_ch is already 0, removing it will cause matched_alphabets to decrease as well
if starting_ch in s1_freq_map:
if s1_freq_map[starting_ch] == 0:
matched_alphabets -= 1
s1_freq_map[starting_ch] += 1
start_idx += 1
# if current window has matched all alphabets in s1, return True immediately
if matched_alphabets == len(s1_freq_map):
return True
return False
can someone please explain why the return doesn’t exit the method here ?
Another not so good answer would be to use sorted() function on both strings after converting them into a list, take Len of s1 and check with two pointer seperated by that Length(s1) on s2,space complexity should not increase in this case, maybe time complexity increases
agreed, even i got a similar approach
This will give you wrong answer, as the relative position of the characters will change after applying the sorting function.
@@yogeshpatil5219 well I don't remember what exactly we are talking about, but it successfully accepted my answer on leetcode that's why added this comment for sure
Very good explanation! Thank you
understood the concept but got lost after line 16.....can someone help??
i fail to understand why elif term is used as in whats the need to increase/decrease the match by 1
just delete the entry O(1) and check if hash is empty each time
Thank You
can you please explain what lines 22 23 and 29 30 are for, I can't understand
The O(26 * n) solution should be good enough. Isn't this a bit of a stretch?
why instead of 26 matches , u have only numb of s1 character matches? can someone explain please
Will interviewer treat the O(26*n) solution as optimal? I afraid messing up somewhere during optimization.
The point isn't to be optimal but to explain how to you got to the solution and what, if any, optimizations could be made. They don't expect you to be correct or optimal. Sometimes there are multiple optimizations that could be made.
The javascript version of this has you memorizing:
const charCode = str.charCodeAt(i);
const alphaIndex = charCode - 97
Anyone pretending they have both a life and can produce this on an interview is lying to themselves.
Just my curiosity, would it be okay to use library during the coding interview like itertools of string permutations then comparing with s2 for submission?
lol
It would be ridiculously slow.
Wonder if just something like this would be enough:
def checkInclusion(self, s1: str, s2: str) -> bool:
l = 0
r = len(s1)
s1Count = collections.Counter(s1)
while r
This is what is Ist approach described here.
Yes! It is so much simpler with dictionary!
I also do not understand why this is not the proposed solution. As long as both sub strings have the same frequency dict, we should return True.
That makes much more sense, thank you for the proposed solution
This is a nice approach. Just want to add that you don't need to calculate the counter each time and instead can be done like this so as to get O(len(s2)) = O(n) runtime:
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
l, r = 0, len(s1)
h1 = Counter(s1)
h2 = Counter(s2[:len(s1)])
while r < len(s2):
if h1 == h2: return True
h2[s2[l]] -= 1
h2[s2[r]] = h2.get(s2[r], 0) + 1
r += 1
l += 1
return h1 == h2
@@aldrinjenson You both are ignoring the idea that s1 could be longer than s2, therefore you'd want to immediately return false.
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
per = [0] * 26
subs = [0] * 26
for char in s1:
per[ord(char) - ord('a')] += 1
l, r = 0, 0
while r < len(s2):
subs[ord(s2[r]) - ord('a')] += 1
if r - l + 1 == len(s1):
if per == subs:
return True
subs[ord(s2[l]) - ord('a')] -= 1
l += 1
r += 1
return False
instead of counting matches, why dont we just check if s1count==s2count
it makes code very less messy
Hi everyone, I have a question. When counting character counts in strings, is it fine to just use HashMaps all the time instead of static Arrays? The space complexity should still be O(1), same as an array of size 26 correct? I think in practice arrays will have less memory overhead, but within the context of an interview there isn't much of a difference.
HashMaps are better since they are implemented by the standard library of most languages (thus a standard and well documented data structure) and it's not a good idea to make your own little implementations when a better solution already exists (if you ever encounter such problems on job)
a map will make it O(1) vs O(26)
Can not we write just else instead of s1Count[index] +1 == s2Count[index] to decrease the matches ?
Yes it is needed :D, After updation matched will be unmatched and unmatched can be matched.
Thanks
Literally last night I was thinking, man I wish Neetcode had a video on Permutation in String #567.... Can you read minds Neetcode?!?
Thanks for the videos!
bueautiful solution
this exceptional logic implemented in c++:
class Solution {
public:
bool checkInclusion(string s1, string s2) {
if(s1.length() > s2.length()) return false;
vector hs1(26, 0);
vector hs2(26, 0);
for(int i = 0; i < s1.length(); i++) {
hs1[s1[i] - 'a']++;
hs2[s2[i] - 'a']++;
}
int matches = 0;
for(int i = 0; i < 26; i++) matches += (hs1[i] == hs2[i]);
int i = 0;
for(int j = s1.length(); j < s2.length(); j++) {
if(matches == 26) return true;
int index = (s2[j] - 'a');
hs2[index]++;
if(hs2[index] == hs1[index]) matches++;
else if(hs2[index] == hs1[index] + 1) matches--;
index = (s2[i] - 'a');
hs2[index]--;
if(hs2[index] == hs1[index]) matches++;
else if(hs2[index] == hs1[index] - 1) matches--;
i++;
}
return matches == 26;
}
};
Can you please explain why you have you chose to subtract ord("a"), or why lower "a" and not some other character ? Thank you
Each characher has a specific ascii code
for example: 'a' = 97 'b' = 98 'd' = 100
If we subtracted the ascii code of 'a' from 'a' itself : We get 97 - 97 = 0 which will be the first index of the array
b - a = 98 - 97 = 1 the second index and so on
this works because we are dealing with lowercase letters only as it was mentioned in the problem
if we would have to deal with uppercase we would subtracted from 'A'
Shorter answer to above - ascii math and getting to array indices faster.
Clear and reset on bad sequence.
def checkInclusion(self, s1: str, s2: str) -> bool:
PCOUNT = Counter(s1)
wcount = Counter()
left = 0
for right in range(len(s2)):
c = s2[right]
if c not in PCOUNT:
wcount.clear()
else:
if not wcount:
left = right
wcount[c] += 1
while wcount[c] > PCOUNT[c]:
wcount[s2[left]] -=1
left += 1
if wcount[c] == PCOUNT[c] and right - left + 1 == len(s1):
return True
return False
i think it can be optimized by : class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
s1Count = [0] * 26
s2Count = [0] * 26
for i in range(len(s1)):
s1Count[ord(s1[i]) - ord('a')] += 1
s2Count[ord(s2[i]) - ord('a')] += 1
if s1Count == s2Count:
return True
for i in range(len(s1), len(s2)):
s2Count[ord(s2[i]) - ord('a')] += 1
s2Count[ord(s2[i - len(s1)]) - ord('a')] -= 1
if s1Count == s2Count:
return True
return False
that's just reverting back to O(26*n) by comparing s1Count == s2Count inside the loop.
6:56 What do you mean by 26 matches? There are only 3 matches correct. I don't understand..
the other 23 will be 0 so they are a match too :)
for people coming from video: Minimum Window Substring - Airbnb Interview Question - Leetcode 76
Below code is exactly followed in above video and its so much relatable and readable
def checkInclusion(self, s1: str, s2: str) -> bool:
if not s1:
return False
countS1 = {}
for c in s1:
countS1[c] = 1 + countS1.get(c,0)
have, need = 0, len(countS1)
window = {}
l = 0
for r in range(len(s2)):
c = s2[r]
window[c] = 1 + window.get(c,0)
if c in countS1 and countS1[c] == window[c]:
have += 1
if need == have:
return True
if r >= sum(countS1.values()) - 1:
char = s2[l]
window[char] -= 1
if char in countS1 and (window[char] - countS1[char]) == -1:
have -= 1
l += 1
return False
Wow. So easy❤
7:02 - start of test case
Instead of creating 2 hashmap, cant we simply create one hashmap for s1 and one stack for s2, whenever we pop the value from s2 stack check if it matches with character in s1 hashmap, if it matches check for the next subsequent popped out character, if it also matches with character in s1 then we can say it matches otherwise not...
That wouldn't work for duplicated characters in S2:
s1 = 'abc'
s2 = 'aab'
so the 'a" would match twice. You'd want to add a check to make sure that it matches only the number of times that it occurs.
at 16:58, I did not understand why in order to check if the number of matches has increased or decreased you gotta check if the count in one hash map + 1 is equal to the count in the other hashmap. Why cant you just use an else statement.
Anyone????
@@shakthivelcr7 What if there were 0 'a' in s1 and 1 'a' in s2? They are not matching. We find another a in s2, so now its 0 2. If we used the else, we would be subtracting matches by 1, when they are not even contributing to matches
@@numwuk thank you!
@@numwuk thank you!
I tried to make similar process to a function while moving window using javascript but didn't work. Can anyone give a solution here?
for(let right = len1; right < len2; right++){
//if matches become 26
if(matches === 26) return true;
movePointer(right, 'right');
movePointer(left, 'left');
left++;
}
function movePointer(i, pointer){
let index = s2.charCodeAt(i) - 'a'.charCodeAt(0);
pointer === 'right' ? s2Count[index]++ : s2Count[index]--;
if(s1Count[index] === s2Count[index]) matches++;
else if((s1Count[index] + pointer === "right"? 1 : (-1) )
=== s2Count[index] ){
matches--;
};
}
For those who were following along with left and right pointers and checking if the frame is valid. Here is the code. I found my implementation to be easier as it looks very similar to other sliding window problems.
public boolean checkInclusion(String s1, String s2) {
if(s1.length()>s2.length()) return false;
int[] freq1 = new int[26];
int[] freq2 = new int[26];
for(int i = 0; i
This was my approach as well as it is more intuitive. Will interviewers care? I feel like some people might nitpick on using an extra O(26) space, but i feel like that is just a minor optimization that requires more leetcode gymnastics.
One optimization to keep the window size equal to the size of s1 always is to increment the r pointer in the else section and update the freq2 array in the same
if len(s1) > len(s2):
return False
freq1 = [0] * 26
freq2 = [0] * 26
for i in range(len(s1)):
freq1[ord(s1[i]) - ord('a')] += 1
l, r = 0, 0
while r < len(s2):
if (r - l + 1) > len(s1):
freq2[ord(s2[l]) - ord('a')] -= 1
l += 1
else:
freq2[ord(s2[r]) - ord('a')] += 1
r += 1
if freq1 == freq2:
return True
return False
I like this one! What kinda language is this?
great explanation but are you sure this is complete solution? it doesnt seem to check for edge case where very last substring of s2 is permutation of the s1 according to my leetcode. loops only twice for when len(s1) = 3 and len(s2) = 5 so last check doesnt make it.
Tried to implement using hashmap but unable to can someone please help?
from string import ascii_lowercase as aslc
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
s1_count, s2_count = {}, {}
for i in range(len(s1)):
s1_count[s1[i]] = 1 + s1_count.get(s1[i],0)
s2_count[s2[i]] = 1 + s2_count.get(s2[i],0)
matches = 0
for i in aslc:
matches += (1 if s1_count.get(i,-1) == s2_count.get(i,-1) else 0)
l = 0
for r in range(len(s1), len(s2)):
if matches == 26: return True
s2_count[s2[r]] =1 + s2_count.get(s2[r],0)
if s1_count.get(s2[r],0) == s2_count.get(s2[r],0):
matches +=1
elif s1_count.get(s2[r],0) + 1 == s2_count.get(s2[r],0):
matches -=1
s2_count[s2[l]] =1 - s2_count.get(s2[l],0)
if s1_count.get(s2[l],0) == s2_count.get(s2[l],0):
matches +=1
elif s1_count.get(s2[l],0) - 1 == s2_count.get(s2[l],0):
matches -=1
l +=1
return matches == 26
hey man please leave a few seconds in the end after u finish talking lmao
Here was my solution, the one shown felt kinda complex:
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
count_s1 = [0] * 26
count_s2 = [0] * 26
# Calculate the number of matches at the start
matches = 26 - len(set(s1))
# Count the frequency of each character in s1
for c in s1:
count_s1[ord(c) - ord('a')] += 1
l, r = 0, 0
while r < len(s2):
right_ind = ord(s2[r]) - ord('a')
# Increment the count for this character in s2's window
count_s2[right_ind] += 1
if count_s1[right_ind] == count_s2[right_ind]:
matches += 1
if matches == 26:
return True
# If the window size equals the length of s1, slide the window
elif len(s1) == (r - l + 1):
left_ind = ord(s2[l]) - ord('a')
# If removing this character would affect the match, decrement matches
if count_s1[left_ind] == count_s2[left_ind]:
matches -= 1
# slide l + update counts
count_s2[left_ind] -= 1
l += 1
# slide r (expand window)
r += 1
return False