How do you solve Permutation in String?

Initialize frequency arrays for s1 and the first window in s2. Count how many characters match in frequency. Slide the window over s2 one character at a time, updating counts and matches accordingly. If at any point matches equals 26 (all characters match), return true. If the loop ends without full match, return false. This approach achieves O(n) time and O(1) space since the alphabet size is fixed.

What pattern does Permutation in String use?

The Pattern: Sliding Window (Fixed-Size Frequency Matching) The Heuristic: When checking for substring permutations or anagrams, maintain frequency counts and a running count of matched characters to detect full matches efficiently as the window slides, avoiding recomputation.

Permutation in String — Sliding Window

Q: What is the time complexity of Permutation in String?

O(n). The algorithm processes each character in s2 exactly once when expanding and once when contracting the window, resulting in a linear pass. Frequency updates and match count adjustments are O(1) operations.

Problem

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

1 ≤ s1.length, s2.length ≤ 10⁴
s1 and s2 consist of lowercase English letters

Example

Input: s1 = "ab", s2 = "eidbaooo"

Output: true

The substring "ba" in s2 is a permutation of s1. The algorithm uses frequency counts of characters in s1 and a sliding window of length equal to s1 over s2. It maintains a count of how many characters match in frequency between s1 and the current window. When all 26 character counts match, it returns true. The critical moment is when the window slides and updates the counts and matches, efficiently checking permutations without sorting or recomputing counts from scratch.

Approach

Straightforward Solution

A brute-force approach checks every substring of s2 of length s1, counts characters, and compares with s1's counts. This is O(n * m) where n = len(s2) and m = len(s1), which is too slow for large inputs.

Core Observation

Two strings are permutations if their character frequency counts are identical. Checking all substrings of s2 of length s1 naively by sorting or counting each time is inefficient.

Path to Optimal

Preview

The key recognition signals are 'permutation', 'substring', and 'contain'. These indicate Sliding Window because the problem reduces to checking if any window of length len(s1) in s2 matches s1's character counts…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize frequency arrays for s1 and the first window in s2. Count how many characters match in frequency…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm processes each character in s2 exactly once when expanding and once when contracting the window, resulting in a linear pass. Frequency updates and match count adjustments are O(1) operations.

Space

O(1)

The frequency arrays have fixed size 26 for lowercase English letters, so auxiliary space does not scale with input size.

Solution

Python

1class Solution:
  def checkInclusion(self, s1: str, s2: str) -> bool:
      if len(s1) > len(s2):
          return False
5
      s1_counts = [0] * 26
      s2_counts = [0] * 26
      for i in range(len(s1)):
          s1_counts[ord(s1[i]) - ord('a')] += 1
          s2_counts[ord(s2[i]) - ord('a')] += 1
11
      matches = 0
      for i in range(26):
          if s1_counts[i] == s2_counts[i]:
              matches += 1
      
      l = 0
      for r in range(len(s1), len(s2)):
          if matches == 26:
              return True
21
          index = ord(s2[r]) - ord('a')
          s2_counts[index] += 1
          if s1_counts[index] == s2_counts[index]:
              matches += 1
          elif s1_counts[index] + 1 == s2_counts[index]:
              matches -= 1
28
          index = ord(s2[l]) - ord('a')
          s2_counts[index] -= 1
          if s1_counts[index] == s2_counts[index]:
              matches += 1
          elif s1_counts[index] - 1 == s2_counts[index]:
              matches -= 1
          l += 1
36
      return matches == 26

Step-by-Step Solution

1

Initialize Frequency Counts for s1 and Initial Window in s2

6s1_counts = [0] * 26
7s2_counts = [0] * 26
8for i in range(len(s1)):
9    s1_counts[ord(s1[i]) - ord('a')] += 1
10    s2_counts[ord(s2[i]) - ord('a')] += 1

Objective

To build frequency arrays for s1 and the first window of s2 to prepare for sliding window comparison.

Key Insight

By precomputing character counts for s1 and the first window in s2, the algorithm sets a baseline for comparison. This avoids recomputing counts from scratch for every window and enables incremental updates as the window slides. Using arrays indexed by character offsets ensures O(1) access and updates.

Interview Quick-Check

Core Logic

Frequency arrays of size 26 represent counts of each lowercase letter, enabling constant-time updates and comparisons.

State & Boundaries

The initial window covers the first len(s1) characters of s2, matching the window size for all subsequent slides.

Common Pitfalls & Bugs

Forgetting to initialize both s1 and s2 counts or misaligning indices leads to incorrect frequency comparisons.

2

Count Initial Matches Between s1 and s2 Frequency Arrays

To determine how many characters currently have matching frequencies between s1 and the initial s2 window.

3

Slide Window Over s2, Update Frequencies and Matches, and Check for Permutation

To incrementally update the sliding window over s2, adjusting frequency counts and matches, and detect if any window is a permutation of s1.

4

Return Final Result Based on Matches After Sliding Window Completion

To return whether the last window checked is a permutation of s1 based on the matches count.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 3 Critical

if len(s1) > len(s2):

Check if s1 is longer than s2, returning false if so.

If s1 is longer, s2 cannot contain any permutation of s1, so returning false immediately avoids unnecessary computation.

Line 19 Critical

if matches == 26:

Check if all characters match, indicating a permutation.

If matches equals 26, the current window is a permutation of s1, so the function returns true immediately.

Line 24 Critical

if s1_counts[index] == s2_counts[index]:

If new character count matches s1's count, increment matches.

This update maintains an accurate count of matching characters, crucial for detecting permutations.

Full line-by-line criticality + rationale for all 29 lines available on Pro.

Test Your Understanding

Why does maintaining a 'matches' count of characters with equal frequency allow the algorithm to detect permutations in O(1) time per window slide?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Permutation in String from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Permutation in String drill

or drill a free problem

1	`class Solution:`
2	`def checkInclusion(self, s1: str, s2: str) -> bool:`
3	`if len(s1) > len(s2):`
4	`return False`
5
6	`s1_counts = [0] * 26`
7	`s2_counts = [0] * 26`
8	`for i in range(len(s1)):`
9	`s1_counts[ord(s1[i]) - ord('a')] += 1`
10	`s2_counts[ord(s2[i]) - ord('a')] += 1`
11
12	`matches = 0`
13	`for i in range(26):`
14	`if s1_counts[i] == s2_counts[i]:`
15	`matches += 1`
16
17	`l = 0`
18	`for r in range(len(s1), len(s2)):`
19	`if matches == 26:`
20	`return True`
21
22	`index = ord(s2[r]) - ord('a')`
23	`s2_counts[index] += 1`
24	`if s1_counts[index] == s2_counts[index]:`
25	`matches += 1`
26	`elif s1_counts[index] + 1 == s2_counts[index]:`
27	`matches -= 1`
28
29	`index = ord(s2[l]) - ord('a')`
30	`s2_counts[index] -= 1`
31	`if s1_counts[index] == s2_counts[index]:`
32	`matches += 1`
33	`elif s1_counts[index] - 1 == s2_counts[index]:`
34	`matches -= 1`
35	`l += 1`
36
37	`return matches == 26`

6	`s1_counts = [0] * 26`
7	`s2_counts = [0] * 26`
8	`for i in range(len(s1)):`
9	`s1_counts[ord(s1[i]) - ord('a')] += 1`
10	`s2_counts[ord(s2[i]) - ord('a')] += 1`