Problem · LC 567

Permutation In String

Medium
◧ Intermediate · fixed-size window with character frequency→ Fixed-Size

How to recognize it

Check if a permutation of s1 exists as a substring in s2. Signal: "permutation", "substring", or "all characters of s1".

The core idea

Use a fixed-size sliding window of size len(s1). Compare character frequencies in the window against s1's frequencies. If they match, s1's permutation is found.

Why It's Tricky

It's not about character order — any permutation counts. You need exact frequency matching for all characters in s1.

The Key Insight

Fixed-size window: maintain frequencies for the current window of size len(s1). Check if frequencies match s1's frequencies. Slide the window by dropping the leftmost char and adding the next.

Step-by-Step Walkthrough

Example: s1="ab", s2="eidbaooo"

Freq(s1) = {a:1, b:1}
Window "ei" → no match
Window "id" → no match
Window "db" → no match
Window "ba" → no match
Window "ao" → no match
Window "oo" → no match
Window "ob" → no match

Wait, let me recount...
Window "ab" (s2[1:3]) → Freq={a:1, b:1} → MATCH! Return true

time O(n)
space O(1)
permutation_in_string
def checkInclusion(s1, s2):
    if len(s1) > len(s2):
        return False
    freq1 = [0] * 26
    window_freq = [0] * 26
    for c in s1:
        freq1[ord(c) - ord('a')] += 1
    for i in range(len(s2)):
        window_freq[ord(s2[i]) - ord('a')] += 1
        if i >= len(s1):
            window_freq[ord(s2[i - len(s1)]) - ord('a')] -= 1
        if freq1 == window_freq:
            return True
    return False

Interview gotchas

  • If len(s1) > len(s2), return false immediately.
  • Frequency must match EXACTLY — order doesn't matter.
  • Window size is fixed at len(s1).

💡 What to Say in the Interview

  • Say: "I'll use a fixed-size sliding window to check frequency matches."
  • Explain: "Maintain frequencies for the current window and s1."
  • Check: "Compare frequencies at each window position."
  • Complexity: "O(n) time, O(1) space (26-letter alphabet)."

↳Variants they'll pivot to

Solve the base problem, then interviewers escalate. These are the usual next steps — knowing the connection is worth more than memorizing each.