You are given two strings s1 and s2.
Return true if s2 contains a permutation of s1, or false otherwise. That means if a permutation of s1 exists as a substring of s2, then return true.
Both strings only contain lowercase letters.
Example 1:
Input: s1 = "abc", s2 = "lecabee"
Output: true Explanation: The substring "cab" is a permutation of "abc" and is present in "lecabee".
Example 2:
Input: s1 = "abc", s2 = "lecaabee"
Output: false
Solution¶
If len(s1) > len(s2), return False.
Initialize frequency maps for s1 (s1map) and the first len(s1) characters of s2 (s2map)
Calculate the initial matches (number of characters with equal frequency in s1map and s2map).
Use a sliding window:
- For each new character in s2, add it to s2map and update matches accordingly.
- Remove the leftmost character from the window and update matches as needed.
- If matches == len(s1map) at any point, return True.
After the loop, return True if matches == len(s1map), otherwise False.
Time Complexity: O(n)
Space Complexity: O(1)
def hasPermutation(s1,s2):
if len(s1)>len(s2):
return False
s1map,s2map={},{}
for i in range(len(s1)):
s1map[s1[i]]=1+s1map.get(s1[i],0) #Initialize s1 frequency map
s2map[s2[i]]=1+s2map.get(s2[i],0) #Initialize first window of s2
matches=0
for c in s1map:
if s1map[c]==s2map.get(c,0):
matches+=1
l=0
for r in range(len(s1),len(s2)):
if matches==len(s1map):
return True
#add new char from right
newChar=s2[r]
s2map[newChar]=1+s2map.get(newChar,0)
if newChar in s1map:
if s2map[newChar]==s1map[newChar]:
matches+=1
elif s2map[newChar]==1+s1map[newChar]:
matches-=1
#remove old char from left
oldChar=s2[l]
l+=1
s2map[oldChar]-=1
if oldChar in s1map:
if s2map[oldChar]==s1map[oldChar]:
matches+=1
elif s2map[oldChar]==s1map[oldChar]-1:
matches-=1
return matches==len(s1map)
hasPermutation("abc","lecabee")
True
hasPermutation( "abc", "lecaabee")
False