Permutation in String

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.

Q: 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.

Medium Sliding Window

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

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. Using fixed-size frequency arrays and a 'matches' counter to track how many characters have matching counts allows O(n) time complexity by updating counts incrementally as the window slides.

Optimal Approach

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.

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.

Pattern Spotlight

Sliding Window (Fixed-Size Frequency Matching)

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.

Solution

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

1class Solution {
  public boolean checkInclusion(String s1, String s2) {
      if (s1.length() > s2.length()) {
          return false;
      }
6
      int[] s1Counts = new int[26];
      int[] s2Counts = new int[26];
      for (int i = 0; i < s1.length(); i++) {
          s1Counts[s1.charAt(i) - 'a']++;
          s2Counts[s2.charAt(i) - 'a']++;
      }
13
      int matches = 0;
      for (int i = 0; i < 26; i++) {
          if (s1Counts[i] == s2Counts[i]) {
              matches++;
          }
      }
20
      int l = 0;
      for (int r = s1.length(); r < s2.length(); r++) {
          if (matches == 26) {
              return true;
          }
26
          int index = s2.charAt(r) - 'a';
          s2Counts[index]++;
          if (s1Counts[index] == s2Counts[index]) {
              matches++;
          } else if (s1Counts[index] + 1 == s2Counts[index]) {
              matches--;
          }
34
          index = s2.charAt(l) - 'a';
          s2Counts[index]--;
          if (s1Counts[index] == s2Counts[index]) {
              matches++;
          } else if (s1Counts[index] - 1 == s2Counts[index]) {
              matches--;
          }
          l++;
      }
44
      return matches == 26;
  }
47}

Step-by-Step Solution

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.

Count Initial Matches Between s1 and s2 Frequency Arrays

12matches = 0
13for i in range(26):
14    if s1_counts[i] == s2_counts[i]:
15        matches += 1

Objective

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

Key Insight

Tracking the number of characters with matching counts allows the algorithm to quickly detect when the entire window matches s1's character distribution. This count is updated incrementally as the window slides, avoiding full array comparisons.

Interview Quick-Check

Core Logic

Increment 'matches' for each character whose frequency in s1 and s2 are equal, establishing the initial match state.

Common Pitfalls & Bugs

Failing to count matches correctly at the start can cause false negatives or positives during window sliding.

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

17l = 0
18for r in range(len(s1), len(s2)):
  if matches == 26:
      return True
  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
  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

Objective

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

Key Insight

The sliding window moves one character at a time. For the new character entering the window, increment its count and update matches accordingly. For the character leaving the window, decrement its count and update matches. This incremental update ensures O(1) work per slide. When matches equals 26, the current window is a permutation, and the algorithm returns true immediately.

Interview Quick-Check

Core Logic

Update counts and matches for the incoming and outgoing characters in the window, and return true if all characters match.

State & Boundaries

The window size remains fixed at len(s1), and the loop iterates from len(s1) to len(s2).

Common Pitfalls & Bugs

Incorrectly updating matches when counts change by one can cause off-by-one errors leading to incorrect results.

Complexity

Each window slide performs O(1) updates, resulting in overall O(n) time complexity.

Return Final Result Based on Matches After Sliding Window Completion

37	`return matches == 26`

Objective

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

Key Insight

If the loop completes without returning true, the final window's matches count is checked. If all characters match, the function returns true; otherwise, false. This ensures correctness even if the last window is the only valid permutation.

Interview Quick-Check

Core Logic

Return true if matches equals 26 after processing all windows, indicating a permutation was found.

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.

Line 26 Critical

elif s1_counts[index] + 1 == s2_counts[index]:

Decrement matches if new character count no longer matches s1's count.

Maintaining matches accurately prevents false positives in permutation detection.

Line 31 Critical

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

Increment matches if outgoing character count now matches s1's count.

Adjusting matches maintains correctness as the window changes.

Line 34 Critical

matches -= 1

Decrement matches if outgoing character count no longer matches s1's count.

Maintains accurate matches count to avoid incorrect permutation detection.

Line 4 Core

return False

Return false when s1 is longer than s2.

This early return handles an edge case efficiently, preventing invalid window sizes and out-of-bounds errors.

Line 9 Core

s1_counts[ord(s1[i]) - ord('a')] += 1

Increment count for s1 character at index i.

Accurately counting s1's characters is critical for correct permutation detection.

Line 10 Core

s2_counts[ord(s2[i]) - ord('a')] += 1

Increment count for s2 character at index i in the initial window.

Capturing the initial window's character distribution allows the algorithm to start with a valid comparison state.

Line 14 Core

if s1_counts[i] == s2_counts[i]:

Check if character counts match for the current letter.

Identifying matching frequencies is essential to increment the matches count correctly.

Line 15 Core

matches += 1

Increment matches if counts are equal for this character.

Accurately counting matches ensures the algorithm can detect when all characters match without full array comparison.

Line 20 Core

return True

Return true when a permutation is found.

Early return optimizes performance by stopping as soon as a valid permutation is detected.

Line 23 Core

s2_counts[index] += 1

Increment frequency count for new character in s2 window.

Updating the count reflects the window's new character composition after sliding right.

Line 25 Core

matches += 1

Check if new character count exceeded s1's count by one.

Detecting when a character's count moves from matching to non-matching allows decrementing matches correctly.

Line 27 Core

matches -= 1

Decrement matches when character count changes from matching to non-matching.

This line ensures matches reflects the true state after the window update.

Line 30 Core

s2_counts[index] -= 1

Decrement frequency count for character leaving the window.

Reflects the window's updated character composition after sliding left.

Line 32 Core

matches += 1

Update matches when outgoing character count matches s1's count.

This line ensures matches stays consistent with the current window state.

Line 33 Core

elif s1_counts[index] - 1 == s2_counts[index]:

Check if outgoing character count changed from matching to non-matching.

Detecting this transition is necessary to decrement matches appropriately.

Line 37 Core

return matches == 26

Return true if all characters match after final window check, else false.

Ensures the function returns the correct result if the last window is a permutation or if no permutation was found.

Line 6 Core

s1_counts = [0] * 26

Initialize frequency array for s1 characters.

This array stores counts of each character in s1, enabling constant-time frequency comparisons.

Line 7 Core

s2_counts = [0] * 26

Initialize frequency array for the first window in s2.

This array tracks counts of characters in the current sliding window of s2, facilitating incremental updates.

Line 12 Core

matches = 0

Initialize matches counter to zero.

Matches tracks how many characters have equal frequency in s1 and the current window, enabling quick permutation checks.

Line 18 Core

for r in range(len(s1), len(s2)):

Iterate right pointer from end of initial window to end of s2.

This loop slides the window across s2, checking each substring of length len(s1) for permutation matches.

Line 22 Core

index = ord(s2[r]) - ord('a')

Calculate index of new character entering the window.

Mapping the character to an index in frequency arrays allows O(1) updates.

Line 29 Core

index = ord(s2[l]) - ord('a')

Calculate index of character leaving the window.

Identifying the outgoing character allows updating frequency counts and matches correctly.

Line 35 Core

l += 1

Move left pointer forward to slide the window.

Advancing the window start is essential for progressing through s2 substrings.

Line 8 Standard

for i in range(len(s1)):

Iterate over the length of s1 to build initial frequency counts.

This loop sets up the baseline frequency counts for both s1 and the initial window in s2, essential for the sliding window comparison.

Line 13 Standard

for i in range(26):

Iterate over all 26 lowercase letters to count matches.

This loop establishes the initial number of matching character frequencies, setting the stage for incremental updates.

Line 17 Standard

l = 0

Initialize left pointer of the sliding window.

The left pointer tracks the start of the current window in s2, necessary for sliding window updates.

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?

Because 'matches' tracks how many characters have identical counts in s1 and the current window, when it reaches 26 (the alphabet size), it guarantees the window is a permutation of s1 without needing to compare entire frequency arrays each time.

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`

1	`class Solution {`
2	`public boolean checkInclusion(String s1, String s2) {`
3	`if (s1.length() > s2.length()) {`
4	`return false;`
5	`}`
6
7	`int[] s1Counts = new int[26];`
8	`int[] s2Counts = new int[26];`
9	`for (int i = 0; i < s1.length(); i++) {`
10	`s1Counts[s1.charAt(i) - 'a']++;`
11	`s2Counts[s2.charAt(i) - 'a']++;`
12	`}`
13
14	`int matches = 0;`
15	`for (int i = 0; i < 26; i++) {`
16	`if (s1Counts[i] == s2Counts[i]) {`
17	`matches++;`
18	`}`
19	`}`
20
21	`int l = 0;`
22	`for (int r = s1.length(); r < s2.length(); r++) {`
23	`if (matches == 26) {`
24	`return true;`
25	`}`
26
27	`int index = s2.charAt(r) - 'a';`
28	`s2Counts[index]++;`
29	`if (s1Counts[index] == s2Counts[index]) {`
30	`matches++;`
31	`} else if (s1Counts[index] + 1 == s2Counts[index]) {`
32	`matches--;`
33	`}`
34
35	`index = s2.charAt(l) - 'a';`
36	`s2Counts[index]--;`
37	`if (s1Counts[index] == s2Counts[index]) {`
38	`matches++;`
39	`} else if (s1Counts[index] - 1 == s2Counts[index]) {`
40	`matches--;`
41	`}`
42	`l++;`
43	`}`
44
45	`return matches == 26;`
46	`}`
47	`}`

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`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Frequency Counts for s1 and Initial Window in s2

Count Initial Matches Between s1 and s2 Frequency Arrays

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

Return Final Result Based on Matches After Sliding Window Completion

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.