Permutation in String

Difficulty: Medium

Problem

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise. In other words, return true if one of s1's permutations is a substring of s2.

Example

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Brute-force approach

Check every substring of s2 with length s1. Sort each and compare with sorted s1.

Steps

  1. Sort s1 to get reference
  2. For each window of size len(s1) in s2
  3. Sort the window and compare with sorted s1
  4. If match found, return true

Time complexity: O(n * k log k) · Space complexity: O(k)

Trade-offs

  • Sorting each window takes O(k log k) — we re-sort overlapping windows from scratch
  • Two permutations have the same character frequencies — we don't need to sort!
  • Can we maintain a running frequency count and just compare frequencies?

Optimal approach

Key insight: Instead of sorting, maintain character frequencies for the window. Track how many characters have matching frequencies between the window and s1. When all match, we found a permutation.

Fixed-size sliding window with frequency map comparison. Maintain a match count for O(1) comparison.

Steps

  1. Build frequency map for s1
  2. Initialize window with first len(s1) characters of s2
  3. Check if initial window matches
  4. Slide: remove left char, add right char, update match count
  5. If matches == required at any point, return true

Time complexity: O(n) · Space complexity: O(1)