Permutation in String | Leetcode #567 | Anagram of string s1 in string s2

This video explains a very important programming interview question which is based on strings and anagrams concept. The problem is to find if there is any permutation of string s1 present in string s2. This problem is same as finding if any substring of string s2 is an anagram of string s1. Two strings can be anagrams if they are of same length. Therefore, in order to check all substrings of s2, we need to only check substrings of size equal to length of s1. For doing this, the best algorithm is to use sliding window approach. I have explained the intuitive sliding window technique using examples and at the end of the video i have explained the CODE for this 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 :)

SIMILAR PROBLEMS:-

[saranyavivekanandan]

Thanks a ton. You're just amazing. Whenever I need a solution for a problem, I immediately look for your video on that particular problem without a second thought, and I never regretted it.

[fatimajaffal]

Yesterday, I didn't have any idea about sliding window technique and learned it from you, today I tried to solve the new problem and I have clearly understood it. (Y)

[soumyadeepdas]

For Python folks!!

class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:

if len(s1)>len(s2):
return False

s1count = [0]*26
s2count = [0]*26

right = 0
left = 0

while(right<len(s1)):

s1count[ord(s1[right]) - ord('a')] +=1
s2count[ord(s2[right]) - ord('a')] +=1

right +=1

right -=1

while(right<len(s2)):

if s1count==s2count:
return True

right +=1
if(right!=len(s2)):
s2count[ord(s2[right]) - ord('a')] +=1

s2count[ord(s2[left]) - ord('a')] -=1
left +=1

return False

[virtualf]

I tried to watch the solution of this question from the video of legends but didnt understand, finally understood the question from this video. Thanks❤.

[yitingg]

I thought about sliding window, did it using 763m, and only beats 6%, damn it, now I am watching this video to see what different technique you used to increase time complexity.

[abhinavghosh]

brother your solution is good as it is
but the runtime will be very high, in java it will touch around 300 ms!
the reason for this is that you are basically generating all possible contiguous substring from s2 of length s1!
try taking use of the previous window, rather than creating a new substring everytime!
[java]
public class Solution {
public boolean checkInclusion(String s1, String s2) {
int len1 = s1.length(), len2 = s2.length();
if (len1 > len2) return false;

int[] count = new int[26];
for (int i = 0; i < len1; i++) {
count[s1.charAt(i) - 'a']++;
count[s2.charAt(i) - 'a']--;
}
if (allZero(count)) return true;

for (int i = len1; i < len2; i++) {
count[s2.charAt(i) - 'a']--;
count[s2.charAt(i - len1) - 'a']++;
if (allZero(count)) return true;
}

return false;
}

private boolean allZero(int[] count) {
for (int i = 0; i < 26; i++) {
if (count[i] != 0) return false;
}
return true;
}
}
[java]

[willturner]

Thanks bhaia for giving such a new method to solve sw

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

[gauravbanerjee]

Thanks a lot for such a crystal clear explanation :)

[Rahul-sxzo]

you're doing a great job sir, i come to refer your solution every time, I'm done solving or trying. You're helping many people, thank you.

[B-AdityaRaj]

thank u sir for, i have learned a new technique today

[AmanKumar-xwkl]

Accha h bro.. ur videos helps a lot.. thanks..

[namansamra]

please share the playlist where i can found more problems related to sliding window.And thanks for this so much superb content

[rajeshbammidy]

Lol, it is very much similar to yesterday's question

[manjunathp]

Python solution
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1)>len(s2):
return False
le=len(s1)
a=''.join(sorted(s1))
for i in range(len(s2)-le+1):
#print(s2[i:i+le])
if
return True
return False

[pragatiagrawal]

Thank you so much for this but I can't understand the reason why that (right!=s2len) check is applied.. Although, I can understand this that it will try to access the elt that doesn't exist and hence it will give the runtime error but the prblm is that I am unable to think of such case if anyone can think of any case where this can happen then I request you to please mention it...Please..thank you in advance

[lindakatunda]

Doing a good job!!!Could you do a video on string processing and another on string parsing.

[Ankitkumar-hukp]

class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n=s1.size();
int m=s2.size();
if (n > m) return false;
vector<int>hash1(26, 0);
vector<int>hash2(26, 0);

for(int i=0;i<n;i++){
hash1[s1[i]-'a']++;
hash2[s2[i]-'a']++;
}

for(int i=n;i<m;i++){
if(hash1==hash2)return true;
hash2[s2[i]-'a']++;
hash2[s2[i-n]-'a']--;
}
return hash1==hash2;
}

};

[SuperMan-rkdm]

What do you mean by "s1hash[s1[right]-'a'] += 1"
Why are we substracting a ?

[ayushgarg]

Sir would you please tell me which software and microphone do you use ?... cuz your voice and writing is so clear