567. Permutation in String
## description
## 567. Permutation in String
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:
1Input: s1 = "ab", s2 = "eidbaooo"
2Output: true
3Explanation: s2 contains one permutation of s1 ("ba").Example 2:
1Input: s1 = "ab", s2 = "eidboaoo"
2Output: false- –1 <= s1.length, s2.length <= 104
- –s1 and s2 consist of lowercase English letters.
Constraints:
## notes
### Intuition
A permutation of s1 in s2 means a substring of s2 has the exact same character frequencies as s1. Slide a fixed-size window across s2 and check if frequencies match.
### Implementation
Use a single frequency array. First, increment for each character in s1, then decrement for the first len(s1) characters of s2. If all zeros, we found a match. Slide the window: increment the count of the character leaving (left), decrement the count of the character entering (right). Check for all zeros at each position.
### Edge-cases
Return early if len(s1) > len(s2). Don't forget to check for a match after the final window position (after the loop exits).
- –Time: O(n) — single pass through s2
- –Space: O(1) — frequency array is fixed at 26 elements
### Complexity
## solution
1class Solution:
2 def char2idx(self, c: str) -> int:
3 return ord(c) - ord('a')
4
5 def checkInclusion(self, s1: str, s2: str) -> bool:
6 if len(s1) > len(s2):
7 return False
8 freq = [0] * 26
9 for c in s1:
10 freq[self.char2idx(c)] += 1
11
12 for i in range(len(s1)):
13 freq[self.char2idx(s2[i])] -= 1
14
15 l, r = 0, len(s1)
16
17 while r < len(s2):
18 if all(x == 0 for x in freq):
19 return True
20
21 # Leaving window
22 freq[self.char2idx(s2[l])] += 1
23 # Entering window
24 freq[self.char2idx(s2[r])] -= 1
25 l += 1
26 r += 1
27
28
29 return all(x == 0 for x in freq)
30
31
32
33
34if __name__ == "__main__":
35 # Include one-off tests here or debugging logic that can be run by running this file
36 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
37 solution = Solution()
38