Permutation in String - Leetcode 567 - Python 

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.

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

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

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

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

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

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

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

hands down best algo tutorials on the internet right now!

i think this solution is very confusing

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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.

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

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

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

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

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

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

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?

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.

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.

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

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

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

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

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

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

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

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

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?

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

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

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

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

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

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 ?

Here's a somewhat simpler solution that I found: def checkInclusion(self, s1: str, s2: str) -> bool: if len(s1) > len(s2): return False count1 = {} count2 = {} # Populate char counts of s1 for char in s1: count1[char] = count1.get(char, 0) + 1 l = 0 for r in range(len(s2)): count2[s2[r]] = count2.get(s2[r], 0) + 1 if (r - l + 1) > len(s1): if count2[s2[l]] == 1: del count2[s2[l]] else: count2[s2[l]] -= 1 l += 1 if count1 == count2: return True return False

Your explanations are always best!!

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

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

man who can think of that lol

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

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

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!

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

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

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

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

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

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

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

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

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

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

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

This is some crazy stuff!

u r genius man

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.

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.

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

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

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 :)

Thank You

it can be easier to set match as len of target

why instead of 26 matches , u have only numb of s1 character matches? can someone explain please

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

Hey, what hardware/software do you use to draw your solutions?

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?

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

The O(26 * n) solution should be good enough. Isn't this a bit of a stretch?

Hi , this is in reference to leetcode 242 (Valid Anagram) , test case 49 is failing. Can you guys point out what's wrong in this code. class Solution { public boolean isAnagram(String s, String t) { HashMapmp1=new HashMap(),mp2=new HashMap(); if(s.length()!=t.length()) return false; for(int i=0;i

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

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

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

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

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?