Permutation in String

Permutation in String medium

Description

Given two strings s1 and s2, return true if s2 contains a permutation of s1 as a substring. In other words, return true if one of the substrings of s2 of length |s1| is an anagram of s1.

Examples

> Case 1:
    s1 = "ab",  s2 = "eidbaooo"
    Output: true
    Explanation: s2 contains "ba", which is a permutation of "ab".
 
> Case 2:
    s1 = "ab",  s2 = "eidboaoo"
    Output: false

Constraints

1 <= s1.length, s2.length <= 10^4
s1 and s2 consist of lowercase English letters.

State design

A permutation of s1 is a length-|s1| window whose character frequency matches s1’s exactly. So:

Window length: fixed = |s1|.
State: frequency arrays need[26] and have[26].
Validity check: all 26 entries of have equal need.

The naïve approach checks all 26 entries on every slide — O(26 × |s2|). The slick approach uses a match counter to track “how many letters have the correct count” in O(1) per shift.

Code — match-counter version

The match counter trick in plain English:

We’re trying to make have[i] == need[i] for all 26 characters.
A matches integer counts how many indices currently satisfy that.
When a character is added, its have[ci] increases by 1. So either it just hit need[ci] (matches++) or it just passed need[ci] (matches—).
Similarly when one leaves.

The whole 26-array compare becomes a single integer check: matches == 26.

Code — simpler “compare arrays” version

For interviews where readability matters more than constant-factor speed, this version is easier to write under pressure:

def check_inclusion(s1, s2):
    if len(s1) > len(s2): return False
    need = [0] * 26
    have = [0] * 26
    for c in s1: need[ord(c) - ord('a')] += 1
    k = len(s1)
    for i in range(k): have[ord(s2[i]) - ord('a')] += 1
    if have == need: return True
    for r in range(k, len(s2)):
        have[ord(s2[r]) - ord('a')] += 1
        have[ord(s2[r - k]) - ord('a')] -= 1
        if have == need: return True
    return False

O(26 × |s2|) — the have == need array compare is the inner cost. For |s2| <= 10^4 it’s still well within limits.

Analysis

Time: O(|s1| + |s2|) with match counter. O(26 × |s2|) with array compare.
Space: O(1) — fixed 26-entry arrays.

Same skin

Find All Anagrams in a String — return all starting indices (not just whether one exists).
Substring with Concatenation of All Words — same idea, but the “alphabet” is the set of words.
Anagram Differences — count of characters to add/remove to turn one into the other.

Longest Substring with K Distinct Find All Anagrams in a String