LeetCode 438. Find All Anagrams in a String (Algorithm Explained)

The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.d...
AlgoCademy - algocademy.com...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/...
Follow Me on X/Twitter - x.com/nickwhit...
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nick....
Become A Member - / @nickwhite
#coding #programming #softwareengineering

[@darod6098]

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!

[@nikhilbisht6503]

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]

thank you for the explanation! I was confused over the increment/decrement notation in the video..

[@nikhilbisht6503]

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

[@codedoctor3265]

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

[@hongchen9833]

thank you very much for the explanation. It's much clear now!

[@fanbu728]

Thank you so much! For a Python coder like me, Nick's ++ and -- notation was really confusing, but your explanation nails it!

[@arnobchowdhury3191]

Great Explanation but please improve the readability of the code.

[@starc701]

bro please dont do things so much directly like incrementing and decrementing ,,then it makes no sense for people who are already confused.

[@mishacalifornia5670]

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)

[@abhiskumar99]

my first thought✌🏿👍

[@professorfinesser4322]

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.

[@gautamgupta9997]

I recently got this same question in my interview but I was unable to solve it 😔 😔 Thank you so much for explaining it

[@prernnajain1532]

Which company asked this?

[@ibrahimitani319]

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

[@linjiafu8546]

I was struggled about the "right - left == p.length()" part. This code is more readable and intuitive.

[@sandipchanda6522]

Thanks Nick. Great Video. Just one request. Please break those single line statements into multiple lines to improve readability of the code

[@shubham28921]

hard to understand code

[@samuelcheng7150]

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?

[@cgerman]

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

[@leomonz]

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?

[@rak590]

confused :-(

[@anandgupta8529]

ridiculous solution, trying to look cooler through that single line statements rather than a readable sol for better explanation.

[@rohitautade1052]

In last if statement , can you please explain why we compare frequency of char at left to be >=0

[@ihopethiscommentisntabusiv4670]

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.

[@MrAjaydivakaran86]

What if a character not in p is present between the anagram characters in s. Does this code handle that scenario?

[@calfland79]

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.

[@brijeshgupta6525]

Nice Explanation! However line no 6 will throw NPE if s is null

[@user-fy4lv4hl3e]

you can write cleaner code , all of those ++ ,-- on the fly like that

[@swagatpatra2139]

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

[@julietgeorge4858]

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.

[@AbhijeetNayak-connect]

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.

[@toprakgungor131]

i dont get it why people are grumpy about ++ and --, it could look better okay but it shouldnt be that hard to understand

[@tjcravey]

You're genuine and honest. I like your content.

[@pranshushrivastava20]

Null check must be done first on line 6 or you will get null pointer error

[@sagarviswakarma3085]

Good explaination, if i were blind i would have understood better. I thought you were gonna find the answer inside the first if() statement.

[@tommytao976]

Put ++ and -- in if statement makes it look cool, but much less readable.

[@lilyh4573]

This was a tricky problem, you did a great job explaining Nick!

[@fazurullachotu2212]

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.

[@fazurullachotu2212]

sorry.. change in previous comment. Count is 0 for the first 3 chars.

[@rancui201]

my favorite youtuber!! super clear explanation and neat code!

[@imtech55]

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.

[@alpeshnikumbh718]

good explaination and code

[@piyushmishra889]

These inline ++ are difficult to understand

[@niwanshumaheshwari4534]

Its a very good solution i must say Give me a new way to think Thankyou so much

[@bonecrusher1792]

# 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

[@hengzhiliu2443]

thank you Nick😁. Your video is always helpful

[@BhaiyaDesi]

Worst way to write a code especially when it comes to increments and decrements.

[@elliotho3015]

Great solution! Thank you Nick :D

[@chengjinfei8139]

++ and - -really confusing

[@harshpatel5812]

Nice explaination and clean code !!!

[@IamProBecauseIcanDoT]

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

[@anuragsrivastava6715]

Very complex way to explain... Not clear at all the algorithm which implemented.... This could have been simple

[@rongguoliang3440]

thank u for good content

[@sase1017]

Good job Nick

[@OmprakashYadavIIT]

too many operations in a single line makes difficult to understand..

[@yashjain992]

Really helpful content!

[@nayandesale9134]

Readability. So difficult

[@choulouchris8788]

一天不看nick 我就浑身难受

[@amir.hessam]

I like Nick but his explanation in this video sucks!

[@jaividyasagarr7110]

Worst Code Readability. Better do next time

[@mnembachambuya3592]

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!

[@highestrankingstarr]

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

[@benakin9172]

the syntax in this is insane! good answer tho

[@JamesHalpert8555]

once again explanation unclear bro....this types of problems can't be explained verbally...please explain with any editor or something like that.

[@vk1618]

Review

[@piyushmishra889]

These inline ++ are difficult to understand