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.
@@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
@@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
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
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
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
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.
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
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
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
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
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 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 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
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.
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
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
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.
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
@@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
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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-jSto0O4AJbM.html
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?
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 ?
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
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
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'
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
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...
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 return False
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.
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)
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
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 :)
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? 🤔
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?