Permutation in String - Leetcode 567 - Python

[@sidchawla7967]

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.

[@SiLintDeath]

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.

[@amandubey5287]

I tried the 0(26*n) but it's showing error for me

[@danielsun716]

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.

[@MinhNguyen-lz1pg]

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.

[@kthtei]

Going too far with the current solution. 26*n should be good enough imo

[@marksmusic7686]

First Neetcode vid I didn't really like, too much boilerplate and setup. Why not just use a hashmap?

[@MrFantasticMunch]

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

[@ngneerin]

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

[@SC2Edu]

yes indeed, I had the same intuition.

[@ashwinpandey5001]

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.

[@radinak5872]

@@ashwinpandey5001 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

[@findingMyself.25yearsago]

@@ashwinpandey5001 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

[@kthtei]

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

[@MrFantasticMunch]

@@mbdev How do you figure? O(26n) eq to O(n)

[@mbdev]

@@MrFantasticMunch (removed my initial comment). thanks. i stand corrected here. O(26) can be considered constant.

[@prasad1204]

beautiful solution

[@LuisRoel]

Wouldn't this be O(len(s1) * len(s2))?

[@MrFantasticMunch]

@@LuisRoel don’t remember the video but n is probably the size of both strings

[@tainhenning1966]

hands down best algo tutorials on the internet right now!

[@rongrongmiao3018]

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.

[@srinadhp]

I never thought I would enjoy solving problems. The way you explain these solutions are invigorating!

[@servantofthelord8147]

Indeed.

[@alternate9160]

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

[@ssz6319]

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

[@samuraijosh1595]

ugly monstrosity

[@hwang1607]

i think this solution is very confusing

[@RIPNANI]

Its easy

[@dattu7944]

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

[@tejasiyer1923]

this is nlogn since you are using the sorted function within the while loop

[@elab4d140]

you can make this run in linear time if you compared frequency array of s1 with frequency array of the window

[@evlntnt1121]

Solved it in 10 minutes days after watching all your videos about sliding windows. It's hard to express what I feel!

[@emachine003]

I managed to figure this out on my own! I think I'm getting better at solving these sorts of problems with your help.

[@naymulhulk840]

making it O(26*n) -> O(n) made it way too complex

[@stylish37]

You are a genius. I saw this video, solved 576 and went on to solve 1004. Thanks a lot!

[@Grawlix99]

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

[@mridulshah7314]

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.

[@Dhanushh]

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

[@DavidDLee]

Interesting solution. Looks like the dict.copy() is O(m*n) in the worst case.

[@sagarverma868]

"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

[@Grawlix99]

@@sagarverma868 `freq` is a dictionary, so look-up for `if s2[i] in freq` will be O(1).

[@ericzheng4815]

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

[@mahesh_kok]

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

[@arda8206]

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

[@EverAfterBreak2]

O(nm) which is fine imo

[@andrewstrady4429]

No matter what actual percentages are displayed after execution at the leetcode, the algorithm is always "pretty efficient")

[@sellygobeze7173]

Great video - I found that completing Valid Anagrams question using an array (instead of a hashmap) helped with my understanding of this solution.

[@yang5843]

This was a lot of boiler plate code for a sliding window solution.

[@v0nnyboy]

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

[@aaqibjavedz2569]

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

[@tenkara101]

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.

[@owaiskazi9941]

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

[@maestro.a]

I like this one! What kinda language is this?

[@shrimpo6416]

You make leetcode questions interesting!

[@ArjunSaxena-wl3qs]

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

[@AdamMrozik-w6u]

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

[@andr3w321]

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

[@CEOofTheHood]

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.

[@johnpaul4301]

Mr neet loooool. Call him sir ya donkey

[@kavyagarikapati8094]

l=0 r=len(s1) counter_s1=Counter(s1) while(r

[@Dyanosis]

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.

[@valentinrafael9201]

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.

[@carloscarrillo201]

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

[@Mamtagoyal27]

This is what is Ist approach described here.

[@samer820]

Yes! It is so much simpler with dictionary!

[@valentinfontanger4962]

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

[@aldrinjenson]

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

[@Dyanosis]

@@aldrinjenson You both are ignoring the idea that s1 could be longer than s2, therefore you'd want to immediately return false.

[@oooo-rc2yf]

I wonder if the regular sliding window solution is enough for interviews, this optimized one is quiet a bit trickier

[@arkamukherjee457]

Code wise, I think they both are similar - you use two hashmaps, and you have some of the similar structure in the code.

[@rydmerlin]

Isn’t the solution you proposed overkill until you’re asked to optimize? And isn’t this method more like to have more mistakes?

[@andrelara2225]

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 } }

[@xBobz99]

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

[@abrarmahi]

This approach would be O(26*n) for anyone wondering

[@devonchia5976]

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.

[@world11191]

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

[@Moccas05]

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

[@eknathyadav8744]

leetcode made it so easy while implementing this solution. But when we implement the solution by ourselves, its not that easy ngl.

[@tomato2699]

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

[@princeofexcess]

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.

[@EduarteBDO]

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

[@fatalsg92]

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

[@sankar6934]

Bro, unga way of explaining is in another level👌, antha parotta soori comedy ah ithula connect pananga patangala. Ur video peaked at that point🤣🤣

[@ahmedamr1124]

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

[@gustavo-yv1gk]

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

[@736939]

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

[@KyuriousBot]

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?

[@danny65769]

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.

[@bhaveshdevjani3278]

True

[@amnaaliahmed4725]

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

[@pranavingale6850]

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

[@Rishipy]

agreed, even i got a similar approach

[@yogeshpatil5219]

This will give you wrong answer, as the relative position of the characters will change after applying the sorting function.

[@pranavingale6850]

@@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

[@josephjoestar4318]

Finally I implemented a solution that imo, is better then yours. It feeling good notwithstanding, probably the first and last time it will happen.

[@TheAlvaryn]

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

[@sf-spark129]

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

[@chandrachurmukherjeejucse5816]

Your explanations are always best!!

[@findingMyself.25yearsago]

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

[@IvanTsurikov]

comparing two arrays of 26 elements is O(1) so really there is no need for the more complicated solution.

[@macro776]

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

[@kennethleung4487]

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?

[@Jr-xs9hy]

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!

[@aayushanupam4471]

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

[@datathatmatters3146]

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

[@xjlonelystar]

man who can think of that lol

[@Ms452123]

I underestimated the question so much and feel like an idiot lol. This was my attempt which only passed the initial test l, r = 0, 1 while r

[@CostaKazistov]

Somewhat similar to today's Leetcode problem 438 - Find All Anagrams in a String

[@lednhatkhanh]

This is extremely detail and easy to follow. Thank you for a great video!

[@minciNashu]

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

[@amynguy]

just delete the entry O(1) and check if hash is empty each time

[@tejanverma6623]

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

[@pinakadhara7650]

This is some crazy stuff!

[@rahulpothula1902]

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; } };

[@gnanaprakashm843]

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 ?

[@IdkIdk-p9i]

u r genius man

[@Deschuttes]

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

[@NeetCode]

Agree it's definitely complex. If it helps there's another problem that uses the same exact technique: kzbin.info/www/bejne/oITXoGOFaaZ9mK8

[@fakecheroom]

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

[@maximushay]

that's just reverting back to O(26*n) by comparing s1Count == s2Count inside the loop.

[@alfredxckh]

Will interviewer treat the O(26*n) solution as optimal? I afraid messing up somewhere during optimization.

[@Dyanosis]

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.

[@HonduranHunk]

This is my solution if anyone is interested. More concise and it makes a lot more sense to me conceptually: class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: s1Count = [0] * 26 s2Count = [0] * 26 for c in s1: s1Count[ord(c) - ord("a")] += 1 # Size of window is length of s1 for i in range(len(s2)): s2Count[ord(s2[i]) - ord("a")] += 1 if i >= len(s1): indexOfCharToRemove = i - len(s1) s2Count[ord(s2[indexOfCharToRemove]) - ord("a")] -= 1 if s1Count == s2Count: return True return False

[@tarushgupta6616]

The explanation is spot on but this is one of those very few times where the code is not neat: if len(s1) > len(s2): return False s1_count = [0] * 26 s2_count = [0] * 26 for i in range(len(s1)): s1_count[ord(s1[i]) - ord('a')] += 1 s2_count[ord(s2[i]) - ord('a')] += 1 for j in range(len(s1), len(s2)): if s1_count == s2_count: return True s2_count[ord(s2[j-len(s1)]) - ord('a')] -= 1 s2_count[ord(s2[j]) - ord('a')] += 1 return s1_count == s2_count This makes the code much neater :)

[@awesome_ashu]

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

[@Marko1402]

Can you please explain why you have you chose to subtract ord("a"), or why lower "a" and not some other character ? Thank you

[@SysMess0]

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'

[@Dyanosis]

Shorter answer to above - ascii math and getting to array indices faster.

[@johns3641]

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

[@abhayk3339]

instead of counting matches, why dont we just check if s1count==s2count it makes code very less messy

[@morgandu183]

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?

[@flamendless]

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? 🤔

[@shensean1784]

it can be easier to set match as len of target

[@aabidibrahimcr7]

class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: if len(s1) > len(s2): return False s1_len = len(s1) s1_counter = [0] * 26 s2_counter = [0] * 26 # Populate s1_counter with character frequencies of s1 for char in s1: s1_counter[ord(char) - ord('a')] += 1 # Initialize the sliding window in s2 for i in range(s1_len): s2_counter[ord(s2[i]) - ord('a')] += 1 # Compare initial window of s2 with s1 if s1_counter == s2_counter: return True # Slide the window through s2 and compare character frequencies for i in range(s1_len, len(s2)): # Add the next character frequency and subtract the frequency of the character leaving the window s2_counter[ord(s2[i]) - ord('a')] += 1 s2_counter[ord(s2[i - s1_len]) - ord('a')] -= 1 # Check if the updated window matches s1's character frequency if s1_counter == s2_counter: return True return False this one is much efficient and better solution

[@shakthivelcr7]

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]

Anyone????

[@numwuk]

@@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

[@yousifsalam]

@@numwuk thank you!

[@jordanjordanov6801]

@@numwuk thank you!

[@soumyadeepdas1536]

For Python folks!! class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: if len(s1)>len(s2): return False s1count = [0]*26 s2count = [0]*26 right = 0 left = 0 while(right

[@oswald3042]

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

[@TheVenom20003]

can you please explain what lines 22 23 and 29 30 are for, I can't understand

[@EE12345]

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.

[@xijinping5064]

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)

[@amynguy]

a map will make it O(1) vs O(26)

[@disha4545]

i fail to understand why elif term is used as in whats the need to increase/decrease the match by 1

[@shenzheng2116]

Genius! You have made a medium question become easy :)

[@Htyagi1998]

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...

[@Dyanosis]

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.

[@TheSahilpadyal]

understood the concept but got lost after line 16.....can someone help??

[@sabukuna]

var checkInclusion = function(s1, s2) { if (s2.length

[@haroldobasi2545]

The question said the length of s1 will be less than or equal to 1 so that caused some confusion

[@ADITYA-fk1zy]

java version: class Solution { public boolean checkInclusion(String s1, String s2) { if(s1.length() > s2.length()) return false; int[] s1Count = new int[26]; int[] s2Count = new int[26]; for(int i = 0;i < s1.length();i++) { s1Count[s1.charAt(i) - 'a'] += 1; s2Count[s2.charAt(i) - 'a'] += 1; } int matches = 0; for(int i = 0;i < 26;i++) { if(s1Count[i] == s2Count[i]) matches++; } int l = 0; for(int r = s1.length();r < s2.length();r++) { if(matches == 26) return true; int index = s2.charAt(r) - 'a'; s2Count[index] += 1; if(s1Count[index] == s2Count[index]) matches++; else if(s1Count[index] + 1 == s2Count[index]) matches -= 1; index = s2.charAt(l) - 'a'; s2Count[index] -= 1; if(s1Count[index] == s2Count[index]) matches++; else if(s1Count[index] - 1 == s2Count[index]) matches -= 1; l += 1; } return matches == 26; } }

[@anasraza2000]

MY SOLUTION : class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: s1 = ''.join(sorted(s1)) for i in range(0, len(s2)-len(s1)+1): b = ''.join(sorted(s2[i:i+len(s1)])) if s1 == b: return True return False Runtime is bad : 4000ms

[@Dyanosis]

Why are you checking the sorted options? All you need to know is if the same characters are present.

[@anasraza2000]

@@Dyanosis I don't know. but this works.