Good video. Thank you. I dont know if it happens to most people or not, but i really dislike incrementing and decremeting counter on the fly instead of using one more line for count++ or count--, i think that because this videos are (at least in some sense?) to explain the algorithms, the readibility is pretty important. Cheers!
This approach is difficult to understand and the use of single line statements with decrements and increments just makes it even more complicated. I have broken down the single line statements and incorporated comments but the intuition is simply not easy to understand through code. Could have explained better in the video. class Solution { public List findAnagrams(String s, String p) { int[] charCount = new int[26];
for(int i = 0; i < p.length(); i++) charCount[p.charAt(i) - 'a']++;
List retList = new ArrayList();
// A variation of sliding window: The left and right end represent the end of a window. // toVisit gives # elements remaining to be visited in the window, till we slide the window. int left = 0, right = 0, toVisit = p.length(); while(right < s.length()){ // If char at right end of window is present in p(charCount) if(charCount[s.charAt(right) - 'a'] >= 1) { toVisit--; } charCount[s.charAt(right) - 'a']--; // Reduce count of char at right end. right++; // Increment right end. if(toVisit == 0) retList.add(left);
// If you have traversed a window completely. Once you've traversed the first p.length() elements // ie. the first window this would always be true, // this is here just so that we completely scan our first window, without incrementing left. if(right - left == p.length()){ if(charCount[s.charAt(left) - 'a'] >= 0){ // This would increment toVisit for characters which were found at right end and were // present in p(charCount) because of which we decremented toVisit in the first if block // and then some characters of p were not found in the window so we need to increment. toVisit++; } charCount[s.charAt(left) - 'a']++; left++; // Just to slide the window. } } return retList; } }
@@ggbong734 More intuitive approach for this question is to compare the entire hash of the current window with that of the original string i.e countChar after every sliding of the window. Time complexity in this case would be = O(h * n), where h is the size of hash i.e countChar which is 26. You can also look into that.
what is wrong my code Nikhil . from collections import defaultdict def find_all_anagrams(s, p): res = [] if len(s)==0 or s=='': return res count_p = defaultdict(int) for char in p: count_p[char]+=1 left = 0 right = 0 count = len(p) while right < len(s): if count_p[s[right]] >= 1: count-=1 count_p[s[right]]-=1 right+=1 if count==0: res.append(left) if right-left==len(p): if count_p[left]>=0: count+=1 count_p[left]+=1 left+=1 return res print(find_all_anagrams("cbaebabacd","abc"))
nice solution. but the ones who will understand ++ and -- used in such a nuanced way probably aren't watching this video. people watching this video will most likely appreciate more direct code that makes the concept clear even if it takes a few more lines.
After making the code a little bit cleaner: class Solution { public List findAnagrams(String s, String p) { int []char_count = new int[26]; for(char a:p.toCharArray()){ char_count[a-'a']++; } List result=new ArrayList(); int left=0; int right = 0; int count=p.length(); while(right=1)count--; char_count[s.charAt(right)-'a']--; right++; if(count==0)result.add(left); if(right-left ==p.length()){ if(char_count[s.charAt(left)-'a']>=0)count++; char_count[s.charAt(left)-'a']++; left++; }
basically we keep a char array(base) to keep count of pattern and use a new array(curr) while sliding over the string. Whenever the arrays match, we store the start index of the current window. Fow sliding window, fill the first window and then subsequent windows. if(Arrays.equals(base, curr)) res.add( i-pattern.length() + 1); POINTS : 1 USE A CHAR ARRAY NOT A HASHMAP, IT'S EASIER TO COMPARE WITH ARRAYS.EQUALS 2 STORE PATTERN'S COUNT IN A CHAR ARRAY(NAMED 'BASE') OF SIZE 26 3 NOW SLIDING WINDOW CONCEPT COMES. IT IS DONE IN 2 STEPS : FIRST WINDOW AND THEN ALL OTHER WINDOWS, TRAVERSE FROM i TILL n (PATTERN LENGTH) AND STORE IN A NEW ARRAY--> FIRST WINDOW AND THEN SLIDE RIGHT BOUNDARY TILL END(STRING LENGTH) --> OTHER WINDOWS 4 COMPARE IF ARRAYS ARE EQUAL WE KEEP THE BASE ARRAY AS A REFERENCE AND THE CURR ARRAY HOLDS THE STATE OF THE CURRENT SLIDING WINDOW 5 IF ARRAYS ARE EQUAL STORE START INDEX OF THIS WINDOW (i-window length) window length = pattern length; ``` public List findAnagrams(String s, String t) { char[] base = new char[26]; List res = new ArrayList(); if(s.length() == 0) return res; int n = t.length(); if(n>s.length()) return res;
for(char c : t.toCharArray()) base[c-'a']++; char[] ch = s.toCharArray(); char[] curr = new char[26]; for(int i=0; i
Honestly, this is fantastic - I was a bit stuck when we got to the decrement and increment on one line but took a day and came back to it. There is no way an interviewer would not think this is a genius way to solve this.
# Python version of Nikhil's implementation. Algorithm is explained below the actual code. # Note: ord() in Python returns ASCII value of character passed in as argument # Time Complexity: O (S) where s is length of s def findAnagrams(self, s, p): result = [] freq = [0] * 26 for ch in p: freq[ord(ch) - ord('a')] += 1 left = 0 right = 0 toVisit = len(p) while right < len(s): if freq[ord(s[right]) - ord('a')] > 0: toVisit -= 1 freq[ord(s[right]) - ord('a')] -= 1 right += 1 if toVisit == 0: result.append(left) if right - left == len(p): if freq[ord(s[left]) - ord('a')] >= 0: toVisit += 1 freq[ord(s[left]) - ord('a')] += 1 left += 1 return result # Algorithm: # 1. result = []. It will store start indices of anagrams of p found in s # # 2. Initialize an array of size 26 (26 letters in alphabet) with all elements # initialized to 0. This array - 'freq' - will serve as a frequency table # for each letter in the alphabet, which will be updated based on p. # # 3. Iterate through each letter in p and increment the corresponding # entry in the frequency table. Note that in order to index into the # corresponding entry, we must subtract 'a' from the letter in p. ie # p = 'abc', s = 'agdb'. We iterate over p and the first iteration focuses # on 'a'. 'a' - 'a' = 0 , so index 0 of freq is incremented. This works # because the ASCII integer values are being used. # # 4. Implement a Sliding Window Mechanism # a) Initialize two pointer variables to 0: left, right # # b) Initialize a variable toVisit to length of p. This tells us how many # characters of p we still need to visit. When it equals 0, this means all # characters of p have been found with the correct frequencies. # # c) Loop through array until right passes the end of the array. # # i. If freq[s[right]-'a'] > 0, then character is in p, so we decrement # toVisit since we just found one of p's characters # # ii. Decrement freq[s[right] - 'a'] # # iii. Increment right # # iv. If toVisit == 0, then all necessary chars found. Append left to # result in this case, since it is the start index of an anagram. # # v. If right - left == length of p, then window is correct length # for a possible anagram. # 1. If freq[s[left]-'a'] >= 0, then increment toVisit. We increment # toVisit because we decremented toVisit earlier when # right pointed to same position as left and # freq[s[right]-'a'] was > 0. # # 2. Increment freq[s[left]-'a'] because we decremented # freq[s[right]-'a'] earlier when right pointed to same position # as left. # # 3. Increment left # d) Return result
As other have mentioned, the inline increment/decrements are very bad from a clarity and readability standpoint. There's no reason you cant simply do the increment/decrement in a separate line. But anyways thanks for the video.
I'm not quite sure I fully understand this sliding window approach. Why not just have the sliding window be a fixed size (the length of p) and move that across the string s and at each iteration, ask whether or not the captured portion of s is an anagram of p? What's the point of moving the left and right pointers?
You will do n loops of the p string where n is the length of the original string to check. It will work but it has a higher complexity and so not optimal
have a hard to understand line 23. I understand you want to restore the char_counts to original value. that only restore one because left++ increment only once. For the next loop inside the while loop, right increment one again so the right - left == p.length() does not meet anymore. so confused.
Solved it in a more brute force manner, but way more readable than ur code in my opinion (C# is my language of choice) none the less Nick I really enjoy your videos - keep doing them! :D public IList FindAnagrams(string s, string p) { List result = new List(); int nS = s.Length; int nP = p.Length; if (String.IsNullOrEmpty(s) || nP > nS) { return result; } int[] pArr = new int[26]; foreach (var c in p) { pArr[c - 'a']++; } for (int i = 0; i
I have a doubt. Count is 0 for the first 2 chars and but the 4 th character also, count is zero even the character is new. i am getting wrong results with this code.
good effort but seems too complicated and complex for those who are beginners in the world of DS/Algo ...for me too the increment decrement on the fly thing made it very much complex.
I hope you know they are copyrighted trademarked licenced material copyright Notice and privacy police Anything you write in anagrams it happens and i am the original anagramist
Good video. Thank you. I dont know if it happens to most people or not, but i really dislike incrementing and decremeting counter on the fly instead of using one more line for count++ or count--, i think that because this videos are (at least in some sense?) to explain the algorithms, the readibility is pretty important.
Cheers!
This approach is difficult to understand and the use of single line statements with decrements and increments just makes it even more complicated. I have broken down the single line statements and incorporated comments but the intuition is simply not easy to understand through code. Could have explained better in the video.
class Solution {
public List findAnagrams(String s, String p) {
int[] charCount = new int[26];
for(int i = 0; i < p.length(); i++) charCount[p.charAt(i) - 'a']++;
List retList = new ArrayList();
// A variation of sliding window: The left and right end represent the end of a window.
// toVisit gives # elements remaining to be visited in the window, till we slide the window.
int left = 0, right = 0, toVisit = p.length();
while(right < s.length()){
// If char at right end of window is present in p(charCount)
if(charCount[s.charAt(right) - 'a'] >= 1) {
toVisit--;
}
charCount[s.charAt(right) - 'a']--; // Reduce count of char at right end.
right++; // Increment right end.
if(toVisit == 0) retList.add(left);
// If you have traversed a window completely. Once you've traversed the first p.length() elements
// ie. the first window this would always be true,
// this is here just so that we completely scan our first window, without incrementing left.
if(right - left == p.length()){
if(charCount[s.charAt(left) - 'a'] >= 0){
// This would increment toVisit for characters which were found at right end and were
// present in p(charCount) because of which we decremented toVisit in the first if block
// and then some characters of p were not found in the window so we need to increment.
toVisit++;
}
charCount[s.charAt(left) - 'a']++;
left++; // Just to slide the window.
}
}
return retList;
}
}
thank you for the explanation! I was confused over the increment/decrement notation in the video..
@@ggbong734 More intuitive approach for this question is to compare the entire hash of the current window with that of the original string i.e countChar after every sliding of the window. Time complexity in this case would be = O(h * n), where h is the size of hash i.e countChar which is 26. You can also look into that.
what is wrong my code Nikhil .
from collections import defaultdict
def find_all_anagrams(s, p):
res = []
if len(s)==0 or s=='':
return res
count_p = defaultdict(int)
for char in p:
count_p[char]+=1
left = 0
right = 0
count = len(p)
while right < len(s):
if count_p[s[right]] >= 1:
count-=1
count_p[s[right]]-=1
right+=1
if count==0:
res.append(left)
if right-left==len(p):
if count_p[left]>=0:
count+=1
count_p[left]+=1
left+=1
return res
print(find_all_anagrams("cbaebabacd","abc"))
thank you very much for the explanation. It's much clear now!
Thank you so much! For a Python coder like me, Nick's ++ and -- notation was really confusing, but your explanation nails it!
Great Explanation but please improve the readability of the code.
You have a bug on line 6: you will get NPE if s is null. To prevent this you want to check for null first:
if (s == null || s.length() == 0)
my first thought✌🏿👍
bro please dont do things so much directly like incrementing and decrementing ,,then it makes no sense for people who are already confused.
nice solution. but the ones who will understand ++ and -- used in such a nuanced way probably aren't watching this video. people watching this video will most likely appreciate more direct code that makes the concept clear even if it takes a few more lines.
Thanks Nick. Great Video. Just one request. Please break those single line statements into multiple lines to improve readability of the code
After making the code a little bit cleaner:
class Solution {
public List findAnagrams(String s, String p) {
int []char_count = new int[26];
for(char a:p.toCharArray()){
char_count[a-'a']++;
}
List result=new ArrayList();
int left=0;
int right = 0;
int count=p.length();
while(right=1)count--;
char_count[s.charAt(right)-'a']--;
right++;
if(count==0)result.add(left);
if(right-left ==p.length()){
if(char_count[s.charAt(left)-'a']>=0)count++;
char_count[s.charAt(left)-'a']++;
left++;
}
}
return result;
}
}
I was struggled about the "right - left == p.length()" part. This code is more readable and intuitive.
basically we keep a char array(base) to keep count of pattern
and use a new array(curr) while sliding over the string.
Whenever the arrays match, we store the start index of the current window.
Fow sliding window, fill the first window and then subsequent windows.
if(Arrays.equals(base, curr)) res.add( i-pattern.length() + 1);
POINTS :
1 USE A CHAR ARRAY NOT A HASHMAP, IT'S EASIER TO COMPARE WITH ARRAYS.EQUALS
2 STORE PATTERN'S COUNT IN A CHAR ARRAY(NAMED 'BASE') OF SIZE 26
3 NOW SLIDING WINDOW CONCEPT COMES. IT IS DONE IN 2 STEPS :
FIRST WINDOW AND THEN ALL OTHER WINDOWS,
TRAVERSE FROM i TILL n (PATTERN LENGTH) AND STORE IN A NEW ARRAY--> FIRST WINDOW
AND THEN SLIDE RIGHT BOUNDARY TILL END(STRING LENGTH) --> OTHER WINDOWS
4 COMPARE IF ARRAYS ARE EQUAL
WE KEEP THE BASE ARRAY AS A REFERENCE AND THE CURR ARRAY HOLDS THE STATE OF THE CURRENT SLIDING WINDOW
5 IF ARRAYS ARE EQUAL STORE START INDEX OF THIS WINDOW
(i-window length) window length = pattern length;
```
public List findAnagrams(String s, String t) {
char[] base = new char[26];
List res = new ArrayList();
if(s.length() == 0) return res;
int n = t.length();
if(n>s.length()) return res;
for(char c : t.toCharArray()) base[c-'a']++;
char[] ch = s.toCharArray(); char[] curr = new char[26];
for(int i=0; i
I recently got this same question in my interview but I was unable to solve it 😔 😔
Thank you so much for explaining it
Which company asked this?
hard to understand code
Honestly, this is fantastic - I was a bit stuck when we got to the decrement and increment on one line but took a day and came back to it. There is no way an interviewer would not think this is a genius way to solve this.
confused :-(
You're genuine and honest. I like your content.
# Python version of Nikhil's implementation. Algorithm is explained below the actual code.
# Note: ord() in Python returns ASCII value of character passed in as argument
# Time Complexity: O (S) where s is length of s
def findAnagrams(self, s, p):
result = []
freq = [0] * 26
for ch in p:
freq[ord(ch) - ord('a')] += 1
left = 0
right = 0
toVisit = len(p)
while right < len(s):
if freq[ord(s[right]) - ord('a')] > 0:
toVisit -= 1
freq[ord(s[right]) - ord('a')] -= 1
right += 1
if toVisit == 0:
result.append(left)
if right - left == len(p):
if freq[ord(s[left]) - ord('a')] >= 0:
toVisit += 1
freq[ord(s[left]) - ord('a')] += 1
left += 1
return result
# Algorithm:
# 1. result = []. It will store start indices of anagrams of p found in s
#
# 2. Initialize an array of size 26 (26 letters in alphabet) with all elements
# initialized to 0. This array - 'freq' - will serve as a frequency table
# for each letter in the alphabet, which will be updated based on p.
#
# 3. Iterate through each letter in p and increment the corresponding
# entry in the frequency table. Note that in order to index into the
# corresponding entry, we must subtract 'a' from the letter in p. ie
# p = 'abc', s = 'agdb'. We iterate over p and the first iteration focuses
# on 'a'. 'a' - 'a' = 0 , so index 0 of freq is incremented. This works
# because the ASCII integer values are being used.
#
# 4. Implement a Sliding Window Mechanism
# a) Initialize two pointer variables to 0: left, right
#
# b) Initialize a variable toVisit to length of p. This tells us how many
# characters of p we still need to visit. When it equals 0, this means all
# characters of p have been found with the correct frequencies.
#
# c) Loop through array until right passes the end of the array.
#
# i. If freq[s[right]-'a'] > 0, then character is in p, so we decrement
# toVisit since we just found one of p's characters
#
# ii. Decrement freq[s[right] - 'a']
#
# iii. Increment right
#
# iv. If toVisit == 0, then all necessary chars found. Append left to
# result in this case, since it is the start index of an anagram.
#
# v. If right - left == length of p, then window is correct length
# for a possible anagram.
# 1. If freq[s[left]-'a'] >= 0, then increment toVisit. We increment
# toVisit because we decremented toVisit earlier when
# right pointed to same position as left and
# freq[s[right]-'a'] was > 0.
#
# 2. Increment freq[s[left]-'a'] because we decremented
# freq[s[right]-'a'] earlier when right pointed to same position
# as left.
#
# 3. Increment left
# d) Return result
As other have mentioned, the inline increment/decrements are very bad from a clarity and readability standpoint. There's no reason you cant simply do the increment/decrement in a separate line. But anyways thanks for the video.
I'm not quite sure I fully understand this sliding window approach. Why not just have the sliding window be a fixed size (the length of p) and move that across the string s and at each iteration, ask whether or not the captured portion of s is an anagram of p? What's the point of moving the left and right pointers?
You will do n loops of the p string where n is the length of the original string to check. It will work but it has a higher complexity and so not optimal
Null check must be done first on line 6 or you will get null pointer error
not sure how it work char_counts[s.charAt(left++) - 'a']++ . so it will add the char 'e' in the first example... then will ruin the logic?
Nice Explanation! However line no 6 will throw NPE if s is null
have a hard to understand line 23. I understand you want to restore the char_counts to original value. that only restore one because left++ increment only once. For the next loop inside the while loop, right increment one again so the right - left == p.length() does not meet anymore. so confused.
This was a tricky problem, you did a great job explaining Nick!
Sorry, but you just copy pasted one of the solutions in discussion thread which is confusing as hell with ++ and -. Didn’t even try to improve that.
In last if statement , can you please explain why we compare frequency of char at left to be >=0
What if a character not in p is present between the anagram characters in s. Does this code handle that scenario?
you can write cleaner code , all of those ++ ,-- on the fly like that
Put ++ and -- in if statement makes it look cool, but much less readable.
Solved it in a more brute force manner, but way more readable than ur code in my opinion (C# is my language of choice) none the less Nick I really enjoy your videos - keep doing them! :D
public IList FindAnagrams(string s, string p)
{
List result = new List();
int nS = s.Length;
int nP = p.Length;
if (String.IsNullOrEmpty(s) || nP > nS)
{
return result;
}
int[] pArr = new int[26];
foreach (var c in p)
{
pArr[c - 'a']++;
}
for (int i = 0; i
my favorite youtuber!! super clear explanation and neat code!
thank you Nick😁. Your video is always helpful
Good explaination, if i were blind i would have understood better. I thought you were gonna find the answer inside the first if() statement.
Its a very good solution i must say
Give me a new way to think
Thankyou so much
I have a doubt. Count is 0 for the first 2 chars and but the 4 th character also, count is zero even the character is new. i am getting wrong results with this code.
sorry.. change in previous comment. Count is 0 for the first 3 chars.
ridiculous solution, trying to look cooler through that single line statements rather than a readable sol for better explanation.
good effort but seems too complicated and complex for those who are beginners in the world of DS/Algo ...for me too the increment decrement on the fly thing made it very much complex.
Great solution! Thank you Nick :D
Worst way to write a code especially when it comes to increments and decrements.
i dont get it why people are grumpy about ++ and --, it could look better okay but it shouldnt be that hard to understand
Nice explaination and clean code !!!
good explaination and code
Good job Nick
too many operations in a single line makes difficult to understand..
thank u for good content
Readability. So difficult
Really helpful content!
These inline ++ are difficult to understand
++ and - -really confusing
the syntax in this is insane! good answer tho
I like Nick but his explanation in this video sucks!
一天不看nick 我就浑身难受
Worst Code Readability. Better do next time
Very complex way to explain... Not clear at all the algorithm which implemented.... This could have been simple
Review
once again explanation unclear bro....this types of problems can't be explained verbally...please explain with any editor or something like that.
dude learn to explain things clearly, you are explaining like you are doing huge favor to public
I hope you know they are copyrighted trademarked licenced material copyright Notice and privacy police Anything you write in anagrams it happens and i am the original anagramist
it might have been better if you could explain the approach before implementing it! you are too fast for some of us! otherwise good job!
These inline ++ are difficult to understand