Description
Return whether s2 contains a contiguous rearrangement of s1. Both strings contain only lowercase English letters.
Solution
def check_inclusion(s1, s2):
if len(s1) > len(s2):
return False
wanted = [0] * 26
window = [0] * 26
for ch in s1:
wanted[ord(ch) - ord("a")] += 1
for i, ch in enumerate(s2):
window[ord(ch) - ord("a")] += 1
if i >= len(s1):
window[ord(s2[i - len(s1)]) - ord("a")] -= 1
if i >= len(s1) - 1 and window == wanted:
return True
return FalseExamples
Example 1
- Input
["ab","eidbaooo"]- Output
true
The substring ba rearranges ab.
Example 2
- Input
["ab","eidboaoo"]- Output
false
No length-two window contains both letters.
Example 3
- Input
["aa","a"]- Output
false
The second string is too short.
Approach
Count the letters in s1 and in a window of equal length in s2. Slide one position at a time by removing the outgoing letter and adding the incoming letter. Equal frequency arrays identify a permutation.
Time & space
O(m + n) time and O(1) auxiliary space for a 26-letter alphabet, where m and n are the two string lengths.