567. Permutation in String
Asked at Meta, Apple, Databricks
Difficulty
Medium
Time
O(n)
Space
O(1)
Pattern
Hash Table
Companies
3
Problem
You are given two strings, s1 and s2. Return true if some arrangement of the letters of s1 appears as a block of consecutive characters inside s2. Otherwise return false.
A permutation of s1 is just s1 with its letters shuffled. So the question is: does s2 contain a window of length len(s1) whose letters are exactly the letters of s1, each used the same number of times?
Two strings are anagrams of each other when they have the same letter counts. So you need a window in s2 that is an anagram of s1. The window must be a real substring — the characters have to sit next to each other, in any order.
Find a window that is an anagram of s1
Constraints
- ●
1 <= s1.length, s2.length <= 10^4 - ●
s1 and s2 consist of lowercase English letters only
Examples
s1 = "ab", s2 = "eidbaooo"trues1 = "ab", s2 = "eidboaoo"falseAsked At
3 companies| Company | Difficulty | |
|---|---|---|
| Meta | Medium | View all Meta questions → |
| Apple | Medium | View all Apple questions → |
| Databricks | Medium | View all Databricks questions → |
How to Think About It
A permutation has the same character frequency as the original string. So you need to find a window in s2 with the same character frequency as s1.
Build a frequency map of s1 (26 lowercase letters). Slide a window of size len(s1) across s2, maintaining a frequency map of the current window. When frequencies match, return true.
Optimized: instead of comparing full frequency maps each time, use a "matches" counter. A match means a character count in the window equals its count in s1. When all 26 characters match, you found a permutation.
Edge cases: s1 longer than s2 (return false), s1 empty (return true), s1 and s2 same length, all characters same.
Optimal Approach
Step 1: If len(s1) > len(s2), return false.
Step 2: Build frequency arrays for s1 and the first window of s2.
Step 3: Count how many of 26 characters have matching counts (matches).
Step 4: Slide the window:
- Add new character on right: if counts now match, increment matches. If they were matching before, decrement.
- Remove old character on left: same logic.
- If matches == 26, return true.
Step 5: Return false.
Time: O(n) where n = len(s2). Space: O(1) (26-element arrays).
Slide a fixed-size window and compare counts
What Trips People Up in Real Interviews
Using a hash map for frequency counts instead of fixed-size arrays. Since the input is lowercase English letters only, int[26] arrays are simpler and faster than a hash map.
Comparing the full frequency array on every slide. The optimized approach uses a matches counter (how many of 26 characters have equal counts) and updates it incrementally, avoiding O(26) comparisons per step.
Forgetting to decrement matches before updating the count. The order matters: if s2Count[idx] == s1Count[idx] before the change, the match is about to break, so decrement first.
Confusing this with "find all anagrams" which returns a list of start indices. This problem returns a boolean, so you can return true as soon as matches == 26 without tracking all positions.
Off-by-one in the window slide: the window should be exactly len(s1) characters wide. When adding s2[i] and removing s2[i - len(s1)], make sure the indices align correctly.
Solution Code
O(n) timefrom collections import Counter
def checkInclusion(s1, s2):
if len(s1) > len(s2):
return False
s1_count = [0] * 26
s2_count = [0] * 26
for i in range(len(s1)):
s1_count[ord(s1[i]) - ord('a')] += 1
s2_count[ord(s2[i]) - ord('a')] += 1
matches = sum(1 for i in range(26) if s1_count[i] == s2_count[i])
for i in range(len(s1), len(s2)):
if matches == 26:
return True
idx_new = ord(s2[i]) - ord('a')
idx_old = ord(s2[i - len(s1)]) - ord('a')
if s2_count[idx_new] == s1_count[idx_new]:
matches -= 1
s2_count[idx_new] += 1
if s2_count[idx_new] == s1_count[idx_new]:
matches += 1
if s2_count[idx_old] == s1_count[idx_old]:
matches -= 1
s2_count[idx_old] -= 1
if s2_count[idx_old] == s1_count[idx_old]:
matches += 1
return matches == 26Frequently Asked Questions
What is the Permutation in String problem?
Given two strings s1 and s2, return true if s2 contains a permutation of s1. In other words, return true if one of s1's permutations is a substring of s2.
How do you solve Permutation in String?
The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Permutation in String?
Permutation in String is asked at Meta, Apple, Databricks. It is a medium difficulty problem.
What are common mistakes on Permutation in String?
- Using a `hash map` for frequency counts instead of fixed-size arrays. Since the input is lowercase English letters only, `int[26]` arrays are simpler and faster than a `hash map`.
- Comparing the full frequency array on every slide. The optimized approach uses a `matches` counter (how many of 26 characters have equal counts) and updates it incrementally, avoiding `O(26)` comparisons per step.
- Forgetting to decrement `matches` before updating the count. The order matters: if `s2Count[idx] == s1Count[idx]` before the change, the match is about to break, so decrement first.
- Confusing this with "find all anagrams" which returns a list of start indices. This problem returns a boolean, so you can return `true` as soon as `matches == 26` without tracking all positions.
- Off-by-one in the window slide: the window should be exactly `len(s1)` characters wide. When adding `s2[i]` and removing `s2[i - len(s1)]`, make sure the indices align correctly.