MediumNeetCode150Hash TableTwo PointersStringSliding Window
Permutation in String
Check if s2 contains a permutation of s1.
Examples
Input
s1 = "ab", s2 = "eidbaooo"
Output
true
'ba' is a permutation of 'ab'.
Constraints
- •
1 <= s1.length, s2.length <= 10^4 - •
s1 and s2 consist of lowercase English letters
Approaches
Sort each window.
CodeT: O(n*k log k) | S: O(k) sorted
def checkInclusion(s1, s2):
import collections
c1=sorted(s1); n=len(s1)
for i in range(len(s2)-n+1):
if sorted(s2[i:i+n])==c1: return True
return FalseFixed window count compare.
CodeT: O(n) | S: O(1) 26-char
def checkInclusion(s1, s2):
import collections
if len(s1)>len(s2): return False
c1=collections.Counter(s1); c2=collections.Counter(s2[:len(s1)])
if c1==c2: return True
for i in range(len(s1),len(s2)):
c2[s2[i]]+=1; c2[s2[i-len(s1)]]-=1
if not c2[s2[i-len(s1)]] del c2[s2[i-len(s1)]]
if c1==c2: return True
return FalseTrack char matches.
Diagram
Count matching frequencies for O(1) compare
CodeT: O(n) | S: O(1)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Sort and Compare | O(n*k log k) | O(k) sorted | Sort each window. |
| Sliding Window + Count | O(n) | O(1) 26-char | Fixed window count compare. |
| Sliding Window + Match Count | O(n) | O(1) | Track char matches. |
Sort and Compare
T: O(n*k log k)S: O(k) sorted
Sort each window.
Sliding Window + Count
T: O(n)S: O(1) 26-char
Fixed window count compare.
Sliding Window + Match Count
T: O(n)S: O(1)
Track char matches.
Common Mistakes
Not handling s1 longer than s2
Off-by-one in window
Wrong count update