567. Permutation in String
Model: qwen3.5:9b
Topics: Two Pointers,Sliding Window
FAANG asked: 1
Acceptance rate: 44.5%
Problem Breakdown
We are given two strings, s1 (the pattern) and s2 (the text). The goal is to determine if any substring of s2 with the same length as s1 contains exactly the same characters in different orders. In other words, does s2 contain a permutation of s1?
Inputs:
- Two strings:
s1,s2. - Constraints: Lowercase English letters only; lengths between 1 and 10,000.
Outputs:
- Boolean (
Trueif found,Falseotherwise).
Implicit Considerations:
- If the length of
s1exceedss2, it’s impossible for a permutation to exist (returnFalse). - Since we are looking for permutations, order within the substring doesn’t matter; only character frequency counts do.
- We need an efficient way to compare frequencies without resorting to sorting every window repeatedly.
Intuition
A brute-force approach would be to iterate through every possible starting position in s2, extract a substring of length equal to len(s1), and check if it is a permutation of s1. Checking for permutations naively (e.g., by sorting both strings or using nested loops) results in time complexity, where is the length of s2 and is the length of s1. Given constraints up to 10,000 characters, this could be too slow.
The key insight here is that we are looking for a sliding window problem. As our window slides one character to the right in s2, only two things change:
- The new character entering from the right side of the window.
- The old character leaving from the left side of the window.
Instead of recalculating frequencies for every substring, we can maintain a frequency map (or counter) and update it incrementally in time per step. We only need to compare our current window’s counts against s1’s target counts after each slide. Since the alphabet size is fixed at 26 lowercase letters, comparing these maps effectively takes constant time relative to input length.
Approach
We will use a Sliding Window technique combined with Frequency Counting (Hash Map or Array).
Step-by-Step Logic:
- Initial Check: If
len(s1) > len(s2), returnFalseimmediately as no substring can exist. - Target Setup: Create a frequency map for characters in
s1. This represents the required counts to match any permutation ofs1. - Window Initialization: Initialize an empty window on
s2(or build it up) and maintain its current character frequencies. We can do this by iterating through the firstlen(s1)characters ofs2. - Comparison Check: After initializing, compare if the target map equals the initial window’s counts. If yes, return
True. - Sliding Loop: Iterate from index
istarting atlen(s1):- Add the new character (
s2[i]) to our current window count. - Remove the old character leaving the window (
s2[i - len(s1)]). - Check if target map equals current window counts after each update. If they match, return
True.
- Add the new character (
- Final Result: If we finish iterating through all windows without a match, return
False.
Data Structure Choice: We use frequency maps (dictionaries or arrays). Given the constraint that inputs only contain lowercase letters (‘a’-‘z’), an array of size 26 is technically optimal for space and speed. However, Python’s collections.Counter provides idiomatic readability with negligible overhead here due to fixed alphabet constraints.
Complexity Analysis
- Time Complexity: where is the length of string
s2. We iterate throughs2once. Operations inside the loop (updating counts and comparing maps) take constant time relative to input size because the number of unique characters in our map is bounded by 26 (, so comparison is effectively ). - Space Complexity: where is the alphabet size. Since inputs are restricted to lowercase English letters, . Thus, space complexity is technically .
Solution
from collections import Counter
def checkInclusion(s1: str, s2: str) -> bool:
# Edge case: if pattern is longer than text, impossible to find permutation
if len(s1) > len(s2):
return False
n = len(s1)
# Frequency map for the target string (s1) and current window in s2
target_counts = Counter(s1)
window_counts = Counter()
# Initialize first window of size equal to s1 length
for i, char in enumerate(s2):
if i < n:
window_counts[char] += 1
# Check initial window match
if target_counts == window_counts:
return True
# Slide the window across s2 starting from index n
left = n - 1
for right in range(n, len(s2)):
new_char = s2[right] # Character entering window
old_char = s2[left] # Character leaving window
# Update counts: add incoming char, remove outgoing char
window_counts[new_char] += 1
if not target_counts[old_char]:
del window_counts[old_char]
left += 1
# Check match after slide. Note: Counter equality checks all keys/values efficiently (O(26))
if target_counts == window_counts:
return True
return False
# Example usage / Test cases can be added here for validation in a real environment
Edge Cases Handled
- Length Mismatch: Explicitly handles
len(s1) > len(s2)by returningFalseimmediately. - Empty Strings: Constraints state length , but the logic naturally degrades gracefully if inputs were empty (Counter of empty string is
{}, comparison works). - No Permutation Found: The loop completes without triggering a match, correctly returning
False. - Duplicate Characters in s1: Handled natively by frequency maps; multiple occurrences are tracked as counts rather than unique keys.