Permutation in String
Asked at Meta, Apple, Databricks
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.
Asked At
| 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.
Visual walkthrough for s1="ab", s2="eidbaooo":
s1_count={a:1, b:1}. Window size=2.
Window "ei": e_count=1, i_count=1. Matches: only characters with count 0 in both maps. Not all 26 match.
Window "id": no match.
Window "db": no match.
Window "ba": b_count=1, a_count=1. Matches all 26 characters. Return true.
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).
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
from 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.