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

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[darod]

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!

[nikhilbisht]

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<Integer> findAnagrams(String s, String p) {
int[] charCount = new int[26];

for(int i = 0; i < p.length(); i++) charCount[p.charAt(i) - 'a']++;

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

[arnobchowdhury]

Great Explanation but please improve the readability of the code.

[mishacalifornia]

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)

[starc]

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

[ibrahimitani]

After making the code a little bit cleaner:

class Solution {
public List<Integer> findAnagrams(String s, String p) {
int []char_count = new int[26];
for(char a:p.toCharArray()){
char_count[a-'a']++;
}
List <Integer>result=new ArrayList<>();
int left=0;
int right = 0;
int count=p.length();
while(right<s.length()){


right++;

if(right-left ==p.length()){


left++;
}

}
return result;
}
}

[professorfinesser]

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.

[swagatpatra]

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<Integer> findAnagrams(String s, String t) {
char[] base = new char[26];
List<Integer> 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<n; i++) curr[ch[i]-'a']++;
if(Arrays.equals(base, curr)) res.add(0);


for(int i = n; i<s.length(); i++){
int prev = i-n;
curr[s.charAt(prev)-'a']--; curr[s.charAt(i)-'a']++;

if(Arrays.equals(base, curr)) res.add(prev+1);
}
return res;
}

[sandipchanda]

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

[brijeshgupta]

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

[gautamgupta]

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

[rohitautade]

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

[samuelcheng]

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?

[julietgeorge]

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.

[lily_h-mj]

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

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

[tjcravey]

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

[ihopethiscommentisntabusiv]

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.

[bonecrusher]

# 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

[calfland]

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.