Core Insight Expand to include new information, then shrink only until the window is valid again.
Common Pitfall Update the best answer only when the window satisfies the problem constraint.
Description
Check if s1's permutation is a substring of s2.
Constraints
- Time Complexity:
O(n) - Space Complexity:
O(1)
Tags
stringsliding-windowhash-maptwo-pointers
Implementation Plan Translate the invariant into these small, testable moves.
- Expand the right edge.
- Update window state.
- Shrink from the left while invalid.
- Record the best valid window.
def checkInclusion(s1, s2):
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
l += 1
return matches == 26