567. Permutation in String — LeetCode(Python)
I got you!
Problem:
Given two strings s1
and s2
, return true
if s2
contains a permutation of s1
, or false
otherwise.
In other words, return true
if one of s1
's permutations is the substring of s2
.
Example 1:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Constraints:
1 <= s1.length, s2.length <= 104
s1
ands2
consist of lowercase English letters.
Solution:
if len(s1) > len(s2):
return False
s1ctr, s2ctr = [0] * 26, [0] * 26
for i in range(len(s1)):
s1ctr[ord(s1[i]) - ord('a')] += 1
s2ctr[ord(s2[i]) - ord('a')] += 1
matches = 0
for i in range(26):
matches += (1 if s1ctr[i] == s2ctr[i] else 0)
l = 0
for r in range(len(s1), len(s2)):
if matches == 26:
return True
# for sliding the right end of the window
index = ord(s2[r]) - ord('a') #find what character has been added to window
s2ctr[index] += 1 #increment character's count in counter array
if s1ctr[index] == s2ctr[index]: #if frequencies same
matches += 1 #then matches++
elif s1ctr[index] + 1 == s2ctr[index]:#if frequency is increased in s2ctr after adding this new character
matches -= 1 #then matches--
# for sliding left end of window
index = ord(s2[l]) - ord('a') # find what character has been removed from window
s2ctr[index] -= 1 # decrement the character's count in counter array
if s1ctr[index] == s2ctr[index]: # if removing that character equals both counts
matches += 1 #mathces ++
elif s1ctr[index] - 1 == s2ctr[index]: #if frequency is decrased in s2ctr after removing from left
matches -= 1 #matches--
l += 1 #keep sliding the window
return matches == 26
Explanation —
We use the sliding window technique here.
We keep two hash maps for s1 and window in s2 of length == len(s1).
The s1ctr dictionary stores the frequency of each element in s1. And the s2ctr dictionary stores the frequency of each element in the window in s2 that we are currently considering.
If the frequency of each element in both hash maps is the same, the string has been found and we return True.
First, we initialize both the hash maps up to length == len(s1). After that, we count the number of matches in both s1ctr and s2ctr.
Now, we slide the window from len(s1), where we are, after initializing the two maps, up to len(s2).
We return True if matches == 26, i.e the frequency of each alphabet is the same in both strings.
We slide the window from the right first, check which character was added, increment it’s count in the map, and update the number of matches accordingly.
Next, we check what character is going to be removed from the left, decrement the character’s count in the map, and update the number of matches accordingly. After that we shrink the window from the left.
Finally, we could have returned False, but we return matches == 26, for the case where matches was made equal to 26 in the last possible window which could not be checked in the for loop.
Time Complexity —
We need a constant amount of space, since we are given that —
s1
ands2
consist of lowercase English letters.
Also, our algorithm requires us to visit each string character at most once, which is a linear time operation.
Thus, if n is the length of the string s2,
Time Complexity: O(n)
Space Complexity: O(26) or O(1) [amortized]