loading

567. Permutation in String — Step-by-Step Visualization

mediumLeetCode #567Hash TableTwo PointersStringSliding Window

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 the substring of `s2`. **Example 1:** Input: `s1 = "ab", s2 = "eidbaooo"` Output: `true` Explanation: `s2` contains one permutation of `s1` ("ba"). **Example 2:** Input: `s1 = "ab", s2 = "eidboaoo"` Output: `false`

Algorithm Pattern

Fixed-Size Sliding Window

Key Idea

A permutation of `s1` must have the exact same length as `s1` and the same character frequencies. We maintain a count of characters for `s1` and a sliding window of length `len(s1)` over `s2`. We update the window's character counts as it moves and check for a match at each step.

Step-by-Step Approach

  1. Count the frequency of each character in `s1`. Let this be `targetCounts`.
  2. Initialize a window of length `len(s1)` starting at index 0 of `s2`.
  3. Count character frequencies in this initial window. Let this be `windowCounts`.
  4. Define a similarity score: how many character frequencies match between `targetCounts` and `windowCounts`. If it's 26, return true.
  5. Slide the window through `s2` by adding one character on the right and removing one from the left.
  6. Update frequencies and similarity score on each slide. If score reaches 26, return true.
  7. Return false if the entire string `s2` is traversed without a match.

Common Gotchas

  • The window must be exactly `len(s1)`. If `len(s1) > len(s2)`, no permutation can exist.
  • Efficiently updating the 'similarity score' (tracking matches) is O(1) per step, making the whole algorithm O(n).

Related Problems

← All problems