Permutation in String
- 3 min read
- LC-Medium
- Sliding Window
Solution
Use two hashmaps, one for each string, where key is character and value is frequency.
Initially, count occurences of character up until length of s1, and then keep track of total matches between both strings by iterating through alphabets.
If matches == 26, then it means we've found a permutation of s1 in s2
Too much to write here but just look at the code and you'll understand
The important thing is, adjusting matches correctly when the sliding window moves
When l increases, a character that was included won't be anymore, so we decrement a value in the s2 map. At this same time, it might've been exactly matching a single character count with s1, and it's not anymore, so update matches accordingly.
Do vice versa for the other side of the sliding window, i.e. when r increases, a new match might occur, or, a match that was already satisfied might not be anymore.
| Time | Space | Explanation |
|---|
O(n) | O(1) | m = len charset, n = len(string) |
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
s1Count, s2Count = [0] * 26, [0] * 26
for i in range(len(s1)):
s1Count[ord(s1[i]) - ord("a")] += 1
s2Count[ord(s2[i]) - ord("a")] += 1
matches = 0
for i in range(26):
matches += 1 if s1Count[i] == s2Count[i] else 0
l = 0
for r in range(len(s1), len(s2)):
if matches == 26:
return True
index = ord(s2[r]) - ord("a")
s2Count[index] += 1
if s1Count[index] == s2Count[index]:
matches += 1
elif s1Count[index] == s2Count[index] - 1:
matches -= 1
index = ord(s2[l]) - ord("a")
s2Count[index] -= 1
if s1Count[index] == s2Count[index]:
matches += 1
elif s1Count[index] == s2Count[index] + 1:
matches -= 1
l += 1
return matches == 26
Solution with defaultdict for counting matches instead of array
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
s1m = defaultdict(lambda: 0)
s2m = defaultdict(lambda: 0)
for i in range(len(s1)):
s1m[s1[i]] += 1
s2m[s2[i]] += 1
matches = 0
for i in range(26):
ch = chr(ord('a') + i)
if s1m[ch] == s2m[ch]:
matches += 1
for r in range(len(s1), len(s2)):
if matches == 26:
return True
ch = s2[r]
s2m[ch] += 1
if s1m[ch] == s2m[ch]:
matches += 1
elif s1m[ch] + 1 == s2m[ch]:
matches -= 1
ch = s2[r - len(s1)]
s2m[ch] -= 1
if s1m[ch] == s2m[ch]:
matches += 1
elif s1m[ch] - 1 == s2m[ch]:
matches -= 1
return matches == 26
