Problem Description

You are given two strings s1 and s2. Your task is to determine if s2 contains any permutation of s1 as a substring.

A permutation means rearranging the letters of a string. For example, "abc" has permutations like "abc", "acb", "bac", "bca", "cab", and "cba".

The problem asks you to return true if any permutation of s1 exists as a contiguous substring within s2, and false otherwise.

For example:

• If s1 = "ab" and s2 = "eidbaooo", the function should return true because s2 contains "ba" which is a permutation of s1.
• If s1 = "ab" and s2 = "eidboaoo", the function should return false because no substring of s2 is a permutation of s1.

The key insight is that you need to find a substring in s2 that has the same length as s1 and contains exactly the same characters with the same frequencies as s1, just potentially in a different order.

Intuition

The key observation is that checking if a substring is a permutation of s1 doesn't require generating all permutations. Instead, we only need to verify that the substring has the same character frequencies as s1.

Think of it this way: if two strings are permutations of each other, they must contain exactly the same characters with exactly the same counts. For instance, "abc" and "bca" both have one 'a', one 'b', and one 'c'.

Since we're looking for a substring of s2 that's a permutation of s1, we know this substring must have the same length as s1. This naturally leads us to consider a sliding window approach - we can examine each substring of s2 with length equal to len(s1).

The naive approach would be to check every possible window by counting character frequencies for each position, but this would be inefficient. Instead, we can maintain a sliding window that moves through s2 one character at a time. As the window slides:

• We add the new character entering the window
• We remove the character leaving the window
• We check if the current window matches s1's character distribution

To efficiently track whether our current window matches s1, we use a counter that starts with the character counts from s1. As we process characters in s2, we decrement counts for characters entering our window and increment counts for characters leaving. We also maintain a need variable that tracks how many distinct characters still need to be matched. When need becomes 0, we've found a valid permutation.

This approach transforms the problem from "find a permutation" to "find a window with matching character frequencies", which can be solved efficiently in linear time.

Learn more about Two Pointers and Sliding Window patterns.

Solution Approach

We implement a sliding window solution that maintains a fixed-size window equal to the length of s1 as it slides through s2.

Data Structures:

• cnt: A Counter (hash map) that tracks the difference between required character counts (from s1) and current window character counts
• need: An integer tracking how many distinct characters still need to be matched

Algorithm Steps:

1. Initialize the counter and need variable:

   • Create cnt = Counter(s1) to store character frequencies from s1
   • Set need = len(cnt), which is the number of distinct characters in s1
   • Store m = len(s1) for the window size

2. Slide the window through s2: For each character c at index i in s2:

   a. Add character to window:

   • Decrement cnt[c] -= 1 (we've seen one more of this character)
   • If cnt[c] becomes 0, it means we've matched all occurrences of character c, so decrement need -= 1

   b. Remove character from window (if window is full):

   • When i >= m, the window size exceeds m, so we need to remove the leftmost character
   • The character to remove is s2[i - m]
   • Increment cnt[s2[i - m]] += 1 (we're losing one of this character)
   • If cnt[s2[i - m]] becomes 1, it means we no longer have enough of this character, so increment need += 1

   c. Check for valid permutation:

   • If need == 0, all character requirements are satisfied, return True

3. Return result:

   • If we finish traversing s2 without finding a valid window, return False

Why this works:

• The cnt values represent the "deficit" or "surplus" of each character
• When cnt[c] = 0, we have exactly the right amount of character c
• When cnt[c] < 0, we have extra occurrences of c (doesn't affect validity)
• When cnt[c] > 0, we're missing occurrences of c
• The window is valid when all characters from s1 have cnt values ≤ 0, which happens when need = 0

Time Complexity: O(n) where n = len(s2), as we visit each character once Space Complexity: O(k) where k is the number of distinct characters in s1

Example Walkthrough

Let's walk through the algorithm with s1 = "ab" and s2 = "eidbaooo".

Initial Setup:

• cnt = Counter("ab") = {'a': 1, 'b': 1}
• need = 2 (we need to match 2 distinct characters)
• m = 2 (window size)

Sliding the window through s2 = "eidbaooo":

i = 0, c = 'e':

• Add 'e' to window: cnt['e'] -= 1 → cnt['e'] = -1
• Since cnt['e'] ≠ 0, need stays at 2
• Window: "e" (size 1)
• Not checking for removal yet (i < m)

i = 1, c = 'i':

• Add 'i' to window: cnt['i'] -= 1 → cnt['i'] = -1
• Since cnt['i'] ≠ 0, need stays at 2
• Window: "ei" (size 2)
• Not checking for removal yet (i < m)

i = 2, c = 'd':

• Add 'd' to window: cnt['d'] -= 1 → cnt['d'] = -1
• Since cnt['d'] ≠ 0, need stays at 2
• Window is now full, remove leftmost character 'e' (at position i-m = 0):
  • cnt['e'] += 1 → cnt['e'] = 0
  • Since cnt['e'] became 0 (not 1), need stays at 2
• Current window: "id"

i = 3, c = 'b':

• Add 'b' to window: cnt['b'] -= 1 → cnt['b'] = 0
• Since cnt['b'] = 0, we've matched all 'b's: need -= 1 → need = 1
• Remove 'i' from window (at position 1):
  • cnt['i'] += 1 → cnt['i'] = 0
  • Since cnt['i'] became 0 (not 1), need stays at 1
• Current window: "db"

i = 4, c = 'a':

• Add 'a' to window: cnt['a'] -= 1 → cnt['a'] = 0
• Since cnt['a'] = 0, we've matched all 'a's: need -= 1 → need = 0
• need = 0 means we found a valid permutation!
• Current window: "ba" (which is indeed a permutation of "ab")
• Return True

The algorithm correctly identifies that "ba" (at positions 3-4 in s2) is a permutation of "ab".

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n), where m is the length of string s1 and n is the length of string s2.

• Creating the Counter for s1 takes O(m) time
• The main loop iterates through each character in s2, which takes O(n) time
• Inside the loop, all operations (dictionary access, arithmetic operations, and comparisons) are O(1)
• Therefore, the total time complexity is O(m + n)

Space Complexity: O(|Σ|), where Σ is the character set.

• The Counter cnt stores at most all unique characters from s1, but since we're dealing with lowercase English letters, the maximum size is bounded by 26
• The space used by the Counter is independent of the input size and depends only on the character set size
• Since the character set is lowercase letters (a constant size of 26), the space complexity is effectively O(1) or constant space

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding When to Update chars_needed

The Problem: A common mistake is updating chars_needed for every change in char_count, rather than only when crossing the zero boundary. Developers might incorrectly write:

# INCORRECT
char_count[char] -= 1
if char_count[char] <= 0:  # Wrong condition!
    chars_needed -= 1

This fails because chars_needed should only change when we transition from "not having enough" to "having exactly enough" (count goes from 1 to 0) or vice versa. If a character appears multiple times and we already have enough, further occurrences shouldn't affect chars_needed.

The Solution: Only update chars_needed when the count crosses zero:

• Decrement when going from positive to zero (just satisfied requirement)
• Increment when going from zero to positive (just lost satisfaction)

# CORRECT
char_count[char] -= 1
if char_count[char] == 0:  # Exactly at boundary
    chars_needed -= 1

Pitfall 2: Incorrect Window Boundary Management

The Problem: Developers often struggle with when to start removing characters from the window. Common mistakes include:

# INCORRECT - Off by one error
if index > window_size:  # Should be >=
    left_char = s2[index - window_size]
  
# INCORRECT - Wrong index calculation
if index >= window_size:
    left_char = s2[index - window_size - 1]  # Wrong!

The Solution: The window should maintain exactly window_size characters. When index >= window_size, we have window_size + 1 characters, so we need to remove the leftmost one at position index - window_size:

# CORRECT
if index >= window_size:
    left_char = s2[index - window_size]

Pitfall 3: Not Handling Characters Not in s1

The Problem: When encountering characters in s2 that don't exist in s1, developers might worry about special handling or think the algorithm breaks. They might try to add checks like:

# UNNECESSARY
if char in char_count:
    char_count[char] -= 1
    # ... more logic

The Solution: Python's Counter automatically handles missing keys by treating them as having a count of 0. When we decrement a non-existent character, it becomes -1, which doesn't affect chars_needed since we only care about transitions through zero. The algorithm naturally handles extra characters by letting their counts go negative without impacting the validity check.

Pitfall 4: Checking Window Validity Too Early

The Problem: Checking if chars_needed == 0 before the window reaches the correct size:

# INCORRECT - Might return True with incomplete window
for index, char in enumerate(s2):
    if chars_needed == 0:  # Checking too early!
        return True
    char_count[char] -= 1
    # ... rest of logic

The Solution: Only check for validity after processing the current character and potentially removing the leftmost character. The window must contain exactly window_size characters when we check:

# CORRECT
for index, char in enumerate(s2):
    # Process current character
    char_count[char] -= 1
    if char_count[char] == 0:
        chars_needed -= 1
  
    # Remove leftmost if needed
    if index >= window_size:
        # ... removal logic
  
    # Now check validity
    if chars_needed == 0:
        return True