Find All Anagrams in a String | Sliding window | Leetcode #438

This video explains a very important programming interview problem which is to find all anagrams of a string P in another string S. We need to record the starting indices of all anagrams of string P in string S and then return the recorded array of indices. The most intuitive approach of solving this problem is by using sliding window technique and i have explained the same using examples. At the end of the video, i have explained the code for the sliding window algorithm. CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[ankurgupta]

i like the way you patiently dry run the whole string other youtubers just dry run one or two steps and say that it in the same way it would give the ans, but you dry run the whole input patiently because of that we students are able to understand the concept clearly

[yevengyklaus]

This is one of the best explanations of sliding window . Thank you !

[mariocamacho]

Best explanations I've seen since I started the May coding challenge. The hardest part to solving these problems is figuring out what they're even asking, you do a great job at telling us what that is. Thank you so much!

[pabloarkadiusz]

I think this can be improved to o(length) creating a variable with the number of letters missing, and when we add or discard a letter just increment or decremenent if the value is equal or not to the needed number of that letter. When that variable value is 0 then add the index to the result. This way we don't need to compare all the alphabet.

[ambrish]

Truly this was the best
I watched solution of others as well they wr too complicated
Please be my mentor

[deepanshu]

I had another approach where i sort p string and iterate over s and for every i calculate substring of length of p srring and sort it and chk if they are same then push i in ans vector .

[sidharthgopalakrishnan]

Amazing intuition behind the sliding window technique ! Thanks for all the lessons you have provided us with for free !

[abhishek]

class Solution {
public String sort(String s){
char[] arr = s.toCharArray();
Arrays.sort(arr);
return String.valueOf(arr);
}
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<Integer>();
String target = sort(p);
for(int i = 0;
String curr = sort(s.substring(i, i+p.length()));
if(curr.equals(target)) res.add(i);
}
return res;

}
}

[Karanyadav-cdsq]

bhai, 2 din se matha khrab ha is easy se question pe geeks for geeks sallo ne answe m pura bawasir kar diya tha. thanks a tone

[balajim]

There was a follow up question in my interview, what if string is not limited to alphabet. In that case comparison is not limited to 26 characters, so total runtime would be n^2. How would you improve the runtime?

[md_aaqil]

Find All Anagrams in a String | Sliding window | Leetcode #438
while(right<len)
{
if(phash == hash)
ans.push_back(left);
right+=1;
if(right!=len)🙂
hash[s[right]-'a'] +=1;
hash[s[left]-'a'] -=1;
left+=1;
}
why are we using if statement(right!=len)🙁??
It is sure that right and len will always be different value sir?
Sorry if i am wrong sir?

[miaohong]

Thank you so much. I implemented a Java version where Arrays.equals(phash, hash) is used to compare two arrays.

public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
if (s == null || s.length() < p.length()) return res;
int[] phash = new int[26];
int[] shash = new int[26];
int window = p.length();
int left = 0;
int right = 0;

while (right < window) {
phash[p.charAt(right) - 'a']++;
shash[s.charAt(right) - 'a']++;
right++;
}

right--;
// for visibility, here is right - -
while (right < s.length()) {
if (Arrays.equals(phash, shash)) {
res.add(left);
}
right++;
if (right != s.length()) {
shash[s.charAt(right) - 'a']++;
}
shash[s.charAt(left) - 'a']--;
// for visibility, here is shash[s.charAt(left) - 'a'] - -
left++;

}
return res;

}

[paritoshpareek]

thanx for such a simplified explanation

[mikedelta]

Thank you for helping us to understand this !

[ChinmayAnaokar-xmci]

Code in C#


public class Solution
{
public IList<int> FindAnagrams(string s, string p)
{
return AppHelper.FindAnagrams(s, p);
}
}
public static class AppHelper
{
public static bool AreEqual(SortedDictionary<char, int>d1, SortedDictionary<char, int>d2)
{
bool keysEqual =
bool valuesEqual =
return keysEqual && valuesEqual;
}
public static IList<int> FindAnagrams(string s, string p)
{
IList<int> lst = new List<int>();
if(p.Length > s.Length)
{
return lst;
}
SortedDictionary<char, int> pCount = new SortedDictionary<char, int>();
SortedDictionary<char, int> sCount = new SortedDictionary<char, int>();
foreach(char c in p)
{
if(!pCount.ContainsKey(c))
{
pCount.Add(c, 1);
}
else
{
pCount[c]++;
}
}
for(int i=0;i<p.Length;i++)
{
if (!sCount.ContainsKey(s[i]))
{
sCount.Add(s[i], 1);
}
else
{
sCount[s[i]]++;
}
}
if(AreEqual(sCount, pCount))
{
lst.Add(0);
}
int left = 0;
for(int right= p.Length; right < s.Length; right++)
{
if
{
sCount.Add(s[right], 1);
}
else
{
sCount[s[right]]++;
}


{
sCount[s[left]]--;
if (sCount[s[left]] == 0)
{
sCount.Remove(s[left]);
}
}
left = left + 1;
if(AreEqual(sCount, pCount))
{
lst.Add(left);
}

}
return lst;
}
}

[swagsterfut]

Alternative solution using unordered map approach in C++:

class Solution {
public:
vector<int> findAnagrams(string s, string p) {

unordered_map<char, int> um;
vector<int> ans;
int i=0, j=0;
for(auto it:p)
um[it]++;
int count=um.size();

while(j < s.size())
{
if(um.find(s[j])!=um.end())
{
um[s[j]]--;
if(um[s[j]]==0) count--;
}

if(j-i+1<p.size()) j++;
else if(j-i+1==p.size())
{
if(count==0)
ans.push_back(i);

if(um.find(s[i])!=um.end())
{
um[s[i]]++;
if(um[s[i]]==1) count++;
}
i++;
j++;
}
}
return ans;
}
};

[yitingg]

Couldn't be more clear, thank you

[shivanisisodia]

Watched so many videos and they are very helpful, explanation is soo good. Thanks and keep it up:)

[amruthap]

great explanation ... 💕👍. Though i have a doubt .If complexity is O(26*n) then eventually it will be O(n) right ?

[manthankhorwal]

we can do this without comparing the hash at each point