> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/algorithms/sliding-window ]
> [project group:: Neetcode 150]
> [difficulty:: medium]
> [status:: done]
> [link:: https://leetcode.com/problems/permutation-in-string/]
> [up:: [[Leetcode MOC]]]
## 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` and `s2` consist of lowercase English letters.
-
## Solution
### Mine
#### Python
```python
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
letters = "abcdefghijklmnopqrstuvwxyz"
i = 0
j = len(s1) - 1
for j in range(j, len(s2)):
flag = True
s3 = s2[i:j+1]
for letter in letters:
if s1.count(letter) != s3.count(letter):
flag = False
break
if flag:
return True
i += 1
return False
```
```python
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
i = 0
j = len(s1) - 1
for j in range(j, len(s2)):
s3 = s2[i:j+1]
if Counter(s1) == Counter(s3):
return True
i += 1
return False
```
This has higher runtime and memory usage than the `.count` solution.
#### Rust
### Neetcode's
```python
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] + 1 == s2Count[index]:
matches -= 1
index = ord(s2[l]) - ord("a")
s2Count[index] -= 1
if s1Count[index] == s2Count[index]:
matches += 1
elif s1Count[index] - 1 == s2Count[index]:
matches -= 1
return matches == 26
```
## Things I Learned
### Neetcode Video
Two solutions: $O(26n) \approx O(n)$ and just $O(n)$.
Look for a substring (window) in `s2` the same size as `s1` . Same thing as looking for anagram [[242. Valid Anagram]].
Trying my own solution starting here based on 242. [[567. Permutation in String#Python|Here]].
I did this based on the `string.count()` method in Python. Without it, you would use a hashmap like [[242. Valid Anagram#^x8bdwa|here]] or, even better, [[242. Valid Anagram#^icdr3v|here]].
The hashmap method uses two hashmaps with all characters of the alphabet as keys, and a count of each character for each input ($O(n)$). Then iterate through the keys (ie a-z; $O(26)$) and keep tally of how many keys match counts. This number should equal the length of `s1` in order to return `True`. This is $O(26) + O(n) \approx O(n)$.
## Scratchpad
My hunch is that we will need to use two sliding windows here, or something to efficiently understand if some substring is any of the permutations of the given string.
Doesn't seem optimal, but what if we had a hash table of `s1`'s letters, and the values were lists of where they've been seen in `s2`. Then get all values, if none are empty and all are contiguous, then return True.
One problem with this is multiple instances of the same letter in `s2` where there are `<= n - 1` instances in `s1` - to fix this we could keep track of the positions in an array of 0s - each index where an `s1` character is present in `s2` is turned to 1 in the position index. This is $O(n)$ extra space, though. Then get all groups of 1 and if the length matches `s1`, True.
Alternatively, we only really care that any of the contiguous groups
- The position index only partially addresses this issue: what if there's a contiguous group, but they consist of repeat characters of which there are more contiguous ones than there are in s1?
For example 1:
`positions = [0, 0, 0, 1, 1, 0, 0, 0]`