⚡Flashcard Drill➔
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

  1. A permutation of s1 must have exactly len(s1) characters, so only fixed-length windows of that size matter.
  2. Compare the character counts of the window with those of s1.
  3. Slide the window one character at a time, adding the entering character and removing the leaving one.
  4. 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; Counter supports direct equality.
  • Skipping the length guard: slicing s2[:k] when k > 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems