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.
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.
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
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.
@@hardboiled_strings You can account for multiple occurrences with a second temp Dict. You then compare the two dict def checkInclusion(self, s1, s2): s1Dict = {} for c in s1: s1Dict[c] = s1Dict.get(c, 0) + 1 l = 0 tempDict = {} for r in range(len(s2)): char = s2[r] if char not in s1Dict: l = r + 1 tempDict = {} continue tempDict[char] = tempDict.get(char, 0) + 1 while tempDict[char] > s1Dict[char]: tempDict[s2[l]] -= 1 l += 1 if tempDict == s1Dict: return True return False
@@hardboiled_strings Here is the solution in account with multiple occurrences also if len(s1) > len(s2): return False window_len = len(s1) s2_len = len(s2) s1_dict = dict(Counter(s1)) s1_dict_len = len(s1_dict) from collections import defaultdict s2_dict = defaultdict(int) matches = 0 left_ind = right_ind = 0 while right_ind < s2_len: ch = s2[right_ind] s2_dict[ch] += 1 if (ch in s1_dict) and s2_dict[ch] == s1_dict[ch]: matches += 1 if matches == s1_dict_len: return True right_ind += 1 # Remove the left part as we move the window # Also making sure once window is formed if right_ind >= window_len: ch = s2[left_ind] if (ch in s1_dict) and s2_dict[ch] == s1_dict[ch]: matches -= 1 s2_dict[ch] -= 1 left_ind += 1 return matches == s1_dict_len
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
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
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
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
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
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
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.
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
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
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
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
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
Intuition: The word "substring" in the problem question hints to me immediately that it may be a "sliding window" problem, as it is contiguous. So I should look for a window of characters in s2 that matches the ASCII/character frequency count of s1. once the window is initialised it will should always maintain fixed length of s1 and constantly checks if the char frequency count of window matches that of s1. if the window finishes traversing the list with no match found, that means there isn't a substring. Approach: i used dictionary to keep track of the frequency of characters within my window. Also created a "target" variable containing the frequency count of s1. So just to reiterate, the idea is if my window matches the target, we have our substring. pointer 'r' traverses s2. 'counter' dictionary counts the frequency of chars in the window using pointer r. once the window size gets bigger than the substring size(s1′ s length), it is an invalid substring due to large size, so we shift pointer 'l' but before that we must update our counter variable with -1 as we no longer have the 'l's character. Also within the counter if the character has 0 frequency, just remove the key entirely (so it can properly match with our "target") if we find our match, immediately return True. At the end of the function we return False. As if the computer reaches that line of the code, it means it didn't find a match to return true earlier. Complexity: Time complexity: Overall, the time complexity is O(m + n*k), where k is constant (26), so it simplifies to O(m + n), where m and n are length of s1 & s2 respectively. Space complexity: the space complexity is O(k), which is constant for the 26 lower-case characters Code: class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: l = 0 counter = {}
if len(s1)>len(s2): return False
target = collections.Counter(s1) for r in range(len(s2)):
if r-l+1> len(s1): counter[s2[l]]-=1 if counter[s2[l]] == 0: del counter[s2[l]] l+=1 counter[s2[r]]=counter.get(s2[r],0)+1 if counter == target: return True return False
I know the array solution can be a bit confusing for the ASCII reference. I translated the reference to a direct lookup with hashmaps, the logic is pretty much the same. I hope this helps someone, it helped me understand the logic of the O(1) solution: class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: if len(s1) > len(s2): return False s1Count = {} s2Count = {} matches = 0 for i in range(26): curChar = chr(ord('a') + i) s1Count[curChar] = 0 s2Count[curChar] = 0 for i in range(len(s1)): s1Count[s1[i]] = 1 + s1Count.get(s1[i], 0) s2Count[s2[i]] = 1 + s2Count.get(s2[i], 0) for i in range(26): curChar = chr(ord('a') + i) if s1Count[curChar] == s2Count[curChar]: matches += 1 L = 0 for R in range(len(s1), len(s2)): if matches == 26: return True s2Count[s2[R]] += 1 if s2Count[s2[R]] == s1Count[s2[R]]: matches += 1 elif s2Count[s2[R]] == s1Count[s2[R]] + 1: matches -= 1 s2Count[s2[L]] -= 1 if s2Count[s2[L]] == s1Count[s2[L]]: matches += 1 elif s2Count[s2[L]] == s1Count[s2[L]] - 1: matches -= 1 L += 1 return matches == 26
I like this solution because the next one on the 150 list requires you to NOT use a O(26*n). So instead of brute force checking 26 each time, we optimise here, and the next question will be much more intuitive once we do this.
My solution with just one dictionary and counts: explanation: 1. Create dictionary of s1 and its counts 2. Do a sliding window for s2. If char from s1_d is in s2, decrement its count plus increment match_count variable. Increment r always 3. If match_count matches len(s1), return True 4. If sliding window exceeds len(s1) before returning true, we decrement matches and move l one step. If character removed by moving l was in s1_d, we increment its count +1 class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: s1_d = {} for char in s1: s1_d[char] = 1 + s1_d.get(char, 0) l, r = 0, 0 match_count = 0 # Tracks the number of characters matched with s1 while r < len(s2): cur = s2[r] if cur in s1_d: s1_d[cur] -= 1 if s1_d[cur] >= 0: match_count += 1 r += 1 # If window size exceeds len(s1), slide the window if r - l > len(s1): left_char = s2[l] if left_char in s1_d: if s1_d[left_char] >= 0: match_count -= 1 s1_d[left_char] += 1 l += 1 if match_count == len(s1): return True return False
if anyone is confused by 'elif s1Count[index] + 1 == s2Count[index]' , we only want to decrement the matches because we found a match during the previous loop of 26, so we only want to adjust the matches count for this occurrence.
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
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.
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?
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
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.
@@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
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 } }
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
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
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
@@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
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 ?
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'
What would be the time complexity if we do this instead? I know sorting makes this O(nlogn) class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: for l in range(len(s2)): r = l + len(s1) sortS2 = ''.join(sorted(s2[l:r])) sortS1 = ''.join(sorted(s1)) if sortS1 in sortS2: return True 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?
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
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!
for those who are wondering why he didn't just use else not else if in case of mismatches you need to know if it was already mismatched or it was matched so if it matched and adding a new element makes it mismatched you need to remove one of the matches but if it was mismatched you don't need to do anything best example try it on ABC and BBBCA
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.
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
In case you want to build your own counter with hashMaps, here's the 1st approach O(26 x n): class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: hashMapS1 = {} hashMapS2 = {} for s in s1: hashMapS1[s] = hashMapS1.get(s, 0) + 1 l, r = 0, len(s1) while r
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
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.
def checkInclusion(self, s1: str, s2: str) -> bool: if len(s2) < len(s1): return False s1_set = Counter(s1) for i in range(len(s2) - len(s1) + 1): left = i right = i + len(s1) if Counter(s2[left:right]) == s1_set: return True return False
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.
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
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?
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
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? 🤔
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
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)
Am I the only one who found this complicated ? That matches made this more complicated. Try following: 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
The code below adapts Neetcode solution to : 1. Use only 1 hashmap (s1Count) 2. Compare only characters of S1 with S2's. It ignores the characters of S2 that are not found in S1. Sorry for comment dump at every line of the code, but that is just to explain the modified approach. class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: if len(s1) > len(s2): return False s1Count = [0] * 26 for i in range(len(s1)): s1Count[ord(s1[i]) - ord("a")] += 1 matchTarget=len([i for i in s1Count if i!=0]) # No of unique chars of S1. Goal is to search for only the chars of S1 in S2. We can't use len(s1) here as S1 can have duplicates s1Count=[None if i==0 else i for i in s1Count] #Of the 26 Chars, the ones not in S1 are marked None. This is useful later in the code winlen , matched = len(s1), 0 #Window length is the size of S1. We move this window along the size of S2. Matched is the counter which how many matches between S1 and S2 happened in this window. Our target is to reach matchTarget. for i in range(len(s2)): #Approach: Every time we find a S2 char which is found in S1, we decrement S1's counter map for that char. If all occurences of char are accounted for, we increment the matched counter by 1. We do the reverse when a char is excluded from the window as we move the window along. index = ord(s2[i]) - ord("a") #Right index of window if s1Count[index]!=None: #This char at this index is found in S1 s1Count[index]-=1 #Decrement the counter for char in S1 hashmap as we just accounted for one of the occurences of char if s1Count[index]==0:#if all occurences of the char are accounted for matched+=1 # increment the match counter #This part of the code is to update window as we shrink the window from left keeping the window length always equal to lenght of S1 if i-winlen>=0: # If the index at S2 is past the S1's length index = ord(s2[i-winlen]) - ord("a") # think of this as left index of window if s1Count[index]!=None: #The char of S2 at its left index is found in S1 if s1Count[index] == 0: #If char at left index contributed to match, matched -= 1 #Decrement match counter as we are excluding this left index s1Count[index] += 1 #Replenish the counter of S1 as left index char is no longer part of the window if matched == matchTarget: #All chars of S1 and their frequencies are matched against that of S2, so return True return True return False
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.
Can someone see if my solution is any good: class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: length = len(s1) - 1 currmap = collections.Counter(s1) l = 0 for r in range(len(s2)): if s2[r] in currmap: currmap[s2[r]] -= 1 if r > length: if s2[l] in currmap: currmap[s2[l]] += 1 l += 1 if all(n == 0 for n in currmap.values()): return True
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.
Going too far with the current solution. 26*n should be good enough imo
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
@@MrFantasticMunch There is no question about that, but still this video is little confusing
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.
@@hardboiled_strings You can account for multiple occurrences with a second temp Dict. You then compare the two dict
def checkInclusion(self, s1, s2):
s1Dict = {}
for c in s1:
s1Dict[c] = s1Dict.get(c, 0) + 1
l = 0
tempDict = {}
for r in range(len(s2)):
char = s2[r]
if char not in s1Dict:
l = r + 1
tempDict = {}
continue
tempDict[char] = tempDict.get(char, 0) + 1
while tempDict[char] > s1Dict[char]:
tempDict[s2[l]] -= 1
l += 1
if tempDict == s1Dict:
return True
return False
@@hardboiled_strings Here is the solution in account with multiple occurrences also
if len(s1) > len(s2):
return False
window_len = len(s1)
s2_len = len(s2)
s1_dict = dict(Counter(s1))
s1_dict_len = len(s1_dict)
from collections import defaultdict
s2_dict = defaultdict(int)
matches = 0
left_ind = right_ind = 0
while right_ind < s2_len:
ch = s2[right_ind]
s2_dict[ch] += 1
if (ch in s1_dict) and s2_dict[ch] == s1_dict[ch]:
matches += 1
if matches == s1_dict_len:
return True
right_ind += 1
# Remove the left part as we move the window
# Also making sure once window is formed
if right_ind >= window_len:
ch = s2[left_ind]
if (ch in s1_dict) and s2_dict[ch] == s1_dict[ch]:
matches -= 1
s2_dict[ch] -= 1
left_ind += 1
return matches == s1_dict_len
hands down best algo tutorials on the internet right now!
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
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
making it O(26*n) -> O(n) made it way too complex
Solved it in 10 minutes days after watching all your videos about sliding windows. It's hard to express what I feel!
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
you can make this run in linear time if you compared frequency array of s1 with frequency array of the window
I managed to figure this out on my own! I think I'm getting better at solving these sorts of problems with your help.
i think this solution is very confusing
Its easy
It's faster than hashmap when you just trying to check if two hashmap equals.
I never thought I would enjoy solving problems. The way you explain these solutions are invigorating!
Indeed.
Great video - I found that completing Valid Anagrams question using an array (instead of a hashmap) helped with my understanding of this solution.
No matter what actual percentages are displayed after execution at the leetcode, the algorithm is always "pretty efficient")
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
This was a lot of boiler plate code for a sliding window solution.
You make leetcode questions interesting!
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
You are a genius. I saw this video, solved 576 and went on to solve 1004. Thanks a lot!
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
O(nm) which is fine imo
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
Using anagram and window technique
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
myDict = dict()
count1 = [0] * 26 # since there're only lowercase letters
for char in s1:
count1[ord(char) - ord('a')] += 1
myDict[tuple(count1)] = 1 + myDict.get(tuple(count1), 0)
l, r = 0, len(s1)
while r < len(s2) + 1:
count2 = [0] * 26
for char in s2[l:r]:
count2[ord(char) - ord('a')] += 1
if tuple(count2) in myDict: # O(1)
return True
l += 1
r += 1
return False
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
this is O(26*n) not the fastest solution
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.
Isn’t the solution you proposed overkill until you’re asked to optimize? And isn’t this method more like to have more mistakes?
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?
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
Intuition:
The word "substring" in the problem question hints to me immediately that it may be a "sliding window" problem, as it is contiguous.
So I should look for a window of characters in s2 that matches the ASCII/character frequency count of s1.
once the window is initialised it will should always maintain fixed length of s1 and constantly checks if the char frequency count of window matches that of s1. if the window finishes traversing the list with no match found, that means there isn't a substring.
Approach:
i used dictionary to keep track of the frequency of characters within my window. Also created a "target" variable containing the frequency count of s1.
So just to reiterate, the idea is if my window matches the target, we have our substring.
pointer 'r' traverses s2. 'counter' dictionary counts the frequency of chars in the window using pointer r. once the window size gets bigger than the substring size(s1′ s length), it is an invalid substring due to large size, so we shift pointer 'l' but before that we must update our counter variable with -1 as we no longer have the 'l's character. Also within the counter if the character has 0 frequency, just remove the key entirely (so it can properly match with our "target")
if we find our match, immediately return True. At the end of the function we return False. As if the computer reaches that line of the code, it means it didn't find a match to return true earlier.
Complexity:
Time complexity:
Overall, the time complexity is O(m + n*k), where k is constant (26), so it simplifies to O(m + n), where m and n are length of s1 & s2 respectively.
Space complexity:
the space complexity is O(k), which is constant for the 26 lower-case characters
Code:
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
l = 0
counter = {}
if len(s1)>len(s2):
return False
target = collections.Counter(s1)
for r in range(len(s2)):
if r-l+1> len(s1):
counter[s2[l]]-=1
if counter[s2[l]] == 0:
del counter[s2[l]]
l+=1
counter[s2[r]]=counter.get(s2[r],0)+1
if counter == target:
return True
return False
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.
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.
I know the array solution can be a bit confusing for the ASCII reference. I translated the reference to a direct lookup with hashmaps, the logic is pretty much the same. I hope this helps someone, it helped me understand the logic of the O(1) solution:
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
s1Count = {}
s2Count = {}
matches = 0
for i in range(26):
curChar = chr(ord('a') + i)
s1Count[curChar] = 0
s2Count[curChar] = 0
for i in range(len(s1)):
s1Count[s1[i]] = 1 + s1Count.get(s1[i], 0)
s2Count[s2[i]] = 1 + s2Count.get(s2[i], 0)
for i in range(26):
curChar = chr(ord('a') + i)
if s1Count[curChar] == s2Count[curChar]:
matches += 1
L = 0
for R in range(len(s1), len(s2)):
if matches == 26:
return True
s2Count[s2[R]] += 1
if s2Count[s2[R]] == s1Count[s2[R]]:
matches += 1
elif s2Count[s2[R]] == s1Count[s2[R]] + 1:
matches -= 1
s2Count[s2[L]] -= 1
if s2Count[s2[L]] == s1Count[s2[L]]:
matches += 1
elif s2Count[s2[L]] == s1Count[s2[L]] - 1:
matches -= 1
L += 1
return matches == 26
I like this solution because the next one on the 150 list requires you to NOT use a O(26*n). So instead of brute force checking 26 each time, we optimise here, and the next question will be much more intuitive once we do this.
My solution with just one dictionary and counts:
explanation:
1. Create dictionary of s1 and its counts
2. Do a sliding window for s2. If char from s1_d is in s2, decrement its count plus increment match_count variable. Increment r always
3. If match_count matches len(s1), return True
4. If sliding window exceeds len(s1) before returning true, we decrement matches and move l one step. If character removed by moving l was in s1_d, we increment its count +1
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
s1_d = {}
for char in s1:
s1_d[char] = 1 + s1_d.get(char, 0)
l, r = 0, 0
match_count = 0 # Tracks the number of characters matched with s1
while r < len(s2):
cur = s2[r]
if cur in s1_d:
s1_d[cur] -= 1
if s1_d[cur] >= 0:
match_count += 1
r += 1
# If window size exceeds len(s1), slide the window
if r - l > len(s1):
left_char = s2[l]
if left_char in s1_d:
if s1_d[left_char] >= 0:
match_count -= 1
s1_d[left_char] += 1
l += 1
if match_count == len(s1):
return True
return False
if anyone is confused by 'elif s1Count[index] + 1 == s2Count[index]' , we only want to decrement the matches because we found a match during the previous loop of 26, so we only want to adjust the matches count for this occurrence.
Bro, unga way of explaining is in another level👌, antha parotta soori comedy ah ithula connect pananga patangala. Ur video peaked at that point🤣🤣
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
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.
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?
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: ruclips.net/video/jSto0O4AJbM/видео.html
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!
leetcode made it so easy while implementing this solution. But when we implement the solution by ourselves, its not that easy ngl.
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
}
}
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
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
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
Finally I implemented a solution that imo, is better then yours. It feeling good notwithstanding, probably the first and last time it will happen.
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
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 ?
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.
What would be the time complexity if we do this instead? I know sorting makes this O(nlogn)
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
for l in range(len(s2)):
r = l + len(s1)
sortS2 = ''.join(sorted(s2[l:r]))
sortS1 = ''.join(sorted(s1))
if sortS1 in sortS2:
return True
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?
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
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
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!
for those who are wondering why he didn't just use else not else if in case of mismatches you need to know if it was already mismatched or it was matched so if it matched and adding a new element makes it mismatched you need to remove one of the matches but if it was mismatched you don't need to do anything best example try it on ABC and BBBCA
comparing two arrays of 26 elements is O(1) so really there is no need for the more complicated solution.
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.
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
In case you want to build your own counter with hashMaps, here's the 1st approach O(26 x n):
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
hashMapS1 = {}
hashMapS2 = {}
for s in s1:
hashMapS1[s] = hashMapS1.get(s, 0) + 1
l, r = 0, len(s1)
while r
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
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.
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s2) < len(s1):
return False
s1_set = Counter(s1)
for i in range(len(s2) - len(s1) + 1):
left = i
right = i + len(s1)
if Counter(s2[left:right]) == s1_set:
return True
return False
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
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
Dict Solution with 0(n) accommodating multiple occurrences
if len(s1) > len(s2):
return False
window_len = len(s1)
s2_len = len(s2)
s1_dict = dict(Counter(s1))
s1_dict_len = len(s1_dict)
from collections import defaultdict
s2_dict = defaultdict(int)
matches = 0
left_ind = right_ind = 0
while right_ind < s2_len:
ch = s2[right_ind]
s2_dict[ch] += 1
if (ch in s1_dict) and s2_dict[ch] == s1_dict[ch]:
matches += 1
if matches == s1_dict_len:
return True
right_ind += 1
# Remove the left part as we move the window
# Also making sure once window is formed
if right_ind >= window_len:
ch = s2[left_ind]
if (ch in s1_dict) and s2_dict[ch] == s1_dict[ch]:
matches -= 1
s2_dict[ch] -= 1
left_ind += 1
return matches == s1_dict_len
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
i fail to understand why elif term is used as in whats the need to increase/decrease the match by 1
can you please explain what lines 22 23 and 29 30 are for, I can't understand
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.
Hey, what hardware/software do you use to draw your solutions?
I just use a computer, mouse and Paint3D.
This solution is at least O(s1 + s2) because you need to set up S1 Count
man who can think of that lol
why instead of 26 matches , u have only numb of s1 character matches? can someone explain please
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;
}
};
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?
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
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 :)
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? 🤔
can someone please explain why the return doesn’t exit the method here ?
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
Somewhat similar to today's Leetcode problem 438 - Find All Anagrams in a String
understood the concept but got lost after line 16.....can someone help??
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)
instead of counting matches, why dont we just check if s1count==s2count
it makes code very less messy
Your explanations are always best!!
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
it can be easier to set match as len of target
just delete the entry O(1) and check if hash is empty each time
Am I the only one who found this complicated ? That matches made this more complicated. Try following:
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
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2): return False
s1_arr, s2_arr = [0] * 26, [0] * 26
for i in range(len(s1)):
s1_arr[ord(s1[i]) - ord('a')] += 1
s2_arr[ord(s2[i]) - ord('a')] += 1
for i in range(len(s1), len(s2)):
if s1_arr == s2_arr: return True
s2_arr[ord(s2[i]) - ord('a')] += 1
s2_arr[ord(s2[i - len(s1)]) - ord('a')] -= 1
return s1_arr == s2_arr
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.
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.
The code below adapts Neetcode solution to :
1. Use only 1 hashmap (s1Count)
2. Compare only characters of S1 with S2's. It ignores the characters of S2 that are not found in S1.
Sorry for comment dump at every line of the code, but that is just to explain the modified approach.
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
s1Count = [0] * 26
for i in range(len(s1)):
s1Count[ord(s1[i]) - ord("a")] += 1
matchTarget=len([i for i in s1Count if i!=0]) # No of unique chars of S1. Goal is to search for only the chars of S1 in S2. We can't use len(s1) here as S1 can have duplicates
s1Count=[None if i==0 else i for i in s1Count] #Of the 26 Chars, the ones not in S1 are marked None. This is useful later in the code
winlen , matched = len(s1), 0 #Window length is the size of S1. We move this window along the size of S2. Matched is the counter which how many matches between S1 and S2 happened in this window. Our target is to reach matchTarget.
for i in range(len(s2)):
#Approach: Every time we find a S2 char which is found in S1, we decrement S1's counter map for that char. If all occurences of char are accounted for, we increment the matched counter by 1. We do the reverse when a char is excluded from the window as we move the window along.
index = ord(s2[i]) - ord("a") #Right index of window
if s1Count[index]!=None: #This char at this index is found in S1
s1Count[index]-=1 #Decrement the counter for char in S1 hashmap as we just accounted for one of the occurences of char
if s1Count[index]==0:#if all occurences of the char are accounted for
matched+=1 # increment the match counter
#This part of the code is to update window as we shrink the window from left keeping the window length always equal to lenght of S1
if i-winlen>=0: # If the index at S2 is past the S1's length
index = ord(s2[i-winlen]) - ord("a") # think of this as left index of window
if s1Count[index]!=None: #The char of S2 at its left index is found in S1
if s1Count[index] == 0: #If char at left index contributed to match,
matched -= 1 #Decrement match counter as we are excluding this left index
s1Count[index] += 1 #Replenish the counter of S1 as left index char is no longer part of the window
if matched == matchTarget: #All chars of S1 and their frequencies are matched against that of S2, so return True
return True
return False
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.
var checkInclusion = function(s1, s2) {
if (s2.length
The question said the length of s1 will be less than or equal to 1 so that caused some confusion
7:02 - start of test case
Can someone see if my solution is any good:
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
length = len(s1) - 1
currmap = collections.Counter(s1)
l = 0
for r in range(len(s2)):
if s2[r] in currmap:
currmap[s2[r]] -= 1
if r > length:
if s2[l] in currmap:
currmap[s2[l]] += 1
l += 1
if all(n == 0 for n in currmap.values()):
return True
return False