NeetCode #232LC-567MediumSliding WindowNC 150NC 250
← Back to All Problems#232 · #567 · Permutation in String(字符串的排列)
📌 Problem Statement & Constraints
Given two strings
s1 and s2, return true if s2 contains a permutation of s1 as a substring. Constraints: 1 <= s1.length, s2.length <= 10^4, lowercase letters.💡 Core Algorithmic Approaches
- A permutation of
s1must have exactlylen(s1)characters, so only fixed-length windows of that size matter. - Compare the character counts of the window with those of
s1. - Slide the window one character at a time, adding the entering character and removing the leaving one.
- Remember to delete zero-count keys from the window counter, otherwise the equality test fails spuriously.
💻 Benchmark Python3 Implementation
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
from collections import Counter
k = len(s1)
if len(s2) < k:
return False
need = Counter(s1)
window = Counter(s2[:k])
if window == need:
return True
for i in range(k, len(s2)):
window[s2[i]] += 1
left = s2[i - k]
window[left] -= 1
if window[left] == 0:
del window[left] # keep the counters comparable
if window == need:
return True
return False⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n) with a constant factor of 26 for each counter comparison.
💾 Space Complexity
O(1): the counters hold at most 26 entries.
⚠️ Interview Pitfalls & Follow-ups
- Not deleting zero-count keys:
Counter({'a': 0}) != Counter({}), so the comparison would fail. This is the most common bug. - Checking the initial window only inside the loop: the first window must be tested before the slide loop starts.
- Using
sorted(window.items()): needlessly expensive;Countersupports direct equality. - Skipping the length guard: slicing
s2[:k]whenk > len(s2)yields a short window, and the comparison would silently fail -- the explicit guard documents the intent.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner