Permutation in String - Leetcode 567 - Python

0:00 - Read the problem
4:10 - Drawing Explanation
11:42 - Coding Explanation

leetcode 567

#microsoft #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[sidchawla]

Just a personal opinion, I think it would have been easier to understand if you had explained the O(26*n) in code and what needs to be changed there for O(n) as an optimization.

[marksmusic]

First Neetcode vid I didn't really like,

too much boilerplate and setup. Why not just use a hashmap?

[ngneerin]

Even better solution is make a map of letters in smaller string with count of letter. And with sliding window iterate and check if character in map. If not Shift window to one next to the mismatch. If all match add 1 to answer. And move sliding window by 1 and keep checking if the new addition there in map until we find a mismatch. In which case we will move window to one next to mismatch

[kthtei]

Nice solution, but this solution is an over kill. Using 2 hashmaps should be fine in interviews. Probably if you're asked to optimize, then you can try this solution.

My solution btw:
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
s1_map = Counter(s1)
s2_map = Counter()

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

for i in range(len(s2)):
s2_map[s2[i]] += 1
if i >= len(s1):
if s2_map[s2[i - len(s1)]] > 1:
s2_map[s2[i - len(s1)]] -= 1
else:
del s2_map[s2[i - len(s1)]]
if s1_map == s2_map:
return True

return False

[dattu]

the straight forward sliding window :
my solution :
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1)>len(s2) : return False
window=len(s1)
sequence1 = sorted(s1)
l=0
r=window-1
while r < len(s2):
sequence=s2[l:r+1]
if sorted(sequence)==sequence1 : return True
l+=1
r+=1
return False

[rongrongmiao]

There is a way that you only need one hashmap. Initialize the hashmap with all chars in s1 count = 1, reduces to min window substring type of problem.

[Grawlix]

Phew, that's a bit of code! I prefer a simpler approach with a single hashmap of only the letters in S1.

Algorithm:
1. Build a frequency dictionary of all characters in S1.
2. Initialize a left pointer to 0.
3. Your right pointer for the sliding window will be part of the [for] loop that iterates over S2. Start the for loop.
If you encounter a character that's in your S1_freq_dict, decrement the frequency.
If the character's new frequency is 0 and the current window size is equivalent to the length of S1, return TRUE!
If the character's new frequency is less than 0, enter a while loop until the frequency is reset to 0:
In the while loop, increment the frequency of the character at the left pointer, then increment the left pointer.
ELSE (character is not in S1_freq_dict)
Update left pointer to right pointer + 1 (i + 1)
Reset S1_freq_dict to a fresh copy of the original dict.

Code:
def checkInclusion(self, s1: str, s2: str) -> bool:
freq = {}
for c in s1:
freq[c] = freq.get(c, 0) + 1

freq_copy = freq.copy()
l = 0
for i in range(len(s2)):
if s2[i] in freq:
freq[s2[i]] -= 1
if freq[s2[i]] == 0 and i - l + 1 == len(s1):
return True
while freq[s2[i]] < 0:
freq[s2[l]] += 1
l += 1
else:
freq = freq_copy.copy()
l = i + 1

return False

[srinadhp]

I never thought I would enjoy solving problems. The way you explain these solutions are invigorating!

[ssz]

Thank you so much for all the great videos. Here is another I did without comparing the whole hashmap:
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
length = len(s1)
left = 0
s1_dict = {}
for c in s1:
s1_dict[c] = 1 + s1_dict.get(c, 0)

s2_dict = {}
for right in range(len(s2)):
if s2[right] not in s1_dict:
s2_dict.clear()
left = right + 1
continue

s2_dict[s2[right]] = 1 + s2_dict.get(s2[right], 0)

while s2_dict[s2[right]] > s1_dict[s2[right]]:
s2_dict[s2[left]] -= 1
left += 1

if (right - left == length - 1) \
and (s2_dict[s2[right]] == s1_dict[s2[right]]):
return True

return False

[hwang]

i think this solution is very confusing

[tainhenning]

hands down best algo tutorials on the internet right now!

[naymulhulk]

making it O(26*n) -> O(n) made it way too complex

[yang]

This was a lot of boiler plate code for a sliding window solution.

[sellygobeze]

Great video - I found that completing Valid Anagrams question using an array (instead of a hashmap) helped with my understanding of this solution.

[andrewstrady]

No matter what actual percentages are displayed after execution at the leetcode, the algorithm is always "pretty efficient")

[shrimpo]

You make leetcode questions interesting!

[andrw]

I found this method more intuitive where you only update s2_freq count if new and old char are different. First decrement matches, then update s2_freq array, then increment matches.

class Solution {

public:
bool checkInclusion(string s1, string s2) {
array<int, 26> s1_freq = {}, s2_freq = {};
int n1 = s1.length(), n2=s2.length(), matches=0;
if (n2 < n1) return false;
for (int i=0; i<n1; ++i) {
s1_freq[s1[i]-'a']++;
s2_freq[s2[i]-'a']++;
}
for (int i=0; i<26; ++i) {
if (s1_freq[i] == s2_freq[i]) matches++;
}
int l=0;
for (int r=n1; r<n2; ++r) {
if (matches == 26) return true;
int old_val = s2[l]-'a';
int new_val = s2[r]-'a';
if (old_val != new_val) {
if (s1_freq[old_val] == s2_freq[old_val]) matches--;
if (s1_freq[new_val] == s2_freq[new_val]) matches--;
s2_freq[old_val]--;
s2_freq[new_val]++;
if (s1_freq[old_val] == s2_freq[old_val]) matches++;
if (s1_freq[new_val] == s2_freq[new_val]) matches++;
}
l++;

}
return matches == 26;
}
};

[xBobz]

Clean approach:

class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
counter1 = collections.Counter(s1)
counter2 =

l = 0
for r in range(len(s1), len(s2)):
if counter1 == counter2:
return True
counter2[s2[l]] -= 1
counter2[s2[r]] += 1
l += 1
return counter1 == counter2

[emachine]

I managed to figure this out on my own! I think I'm getting better at solving these sorts of problems with your help.

[CEOofTheHood]

Hi Mr.Neet, you have about covered most graph topic but one that seems to be missing is strongly connected components. Would really appreciate it if you could teach that when you have time.