0567.Permutation in String

• Link: 567. Permutation in String - Medium
• Track: NeetCode150

Question

Restate the problem

• Given two strings s1 and s2
• Return True if some permutation of s1 appears as a substring in s2; otherwise return False.

In other words, check whether s2 contains a substring of length len(s1) whose character frequency is exactly the same as s1.

Edge Case

• len(s1) > len(s2) → impossible, return False
• s1 and s2 contain only lowercase English letters
• We need an exact frequency match, not just the same set of characters

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Sliding window	$O(n)$	$O(1)$

Method 1 - Sliding window

The key idea is to use a frequency array of size 26 to record the character counts.

Approach

• Use a fixed-size sliding window of length len(s1) over s2.
• First, count the frequency of each character in s1 using an array need of size 26.
  • need[i] means how many more of that character are still needed for the current window to match s1.
• As the right pointer expands the window:
  • subtract the new character from need
• If the window becomes longer than len(s1):
  • remove the left character from the window
  • add it back to need
• If at any point need == [0] * 26, then the current window has exactly the same character counts as s1, so return True.

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$
  • Fixed size 26

Code

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        need = [0] * 26
        zero = [0] * 26
        for char in s1:
            idx = ord(char) - ord('a')
            need[idx] += 1
 
        left = right = 0
        while right < len(s2):
            idx = ord(s2[right]) - ord('a') # e - a
            need[idx] -= 1
            
            if right - left + 1 > len(s1):
                idx = ord(s2[left]) - ord('a')
                need[idx] += 1
                left += 1
            
            if need == zero:
                return True
            
            right += 1
        
        return False

---

Mistake

• fixed-size sliding window