Permutation in String

MediumSliding WindowHash TableStringSliding Window

Problem

You are given two strings, a short pattern and a longer text. Determine whether the text contains a contiguous run of characters that is some rearrangement of the pattern: a permutation of the exact same letters, in any order.

Example. For pattern "ab" and text "eidbaooo", the substring "ba" is a rearrangement of "ab", so the answer is true.

Key idea

Generating every permutation of the pattern and searching for each one is combinatorially expensive, and separately checking every substring of the text for a full anagram match from scratch costs a lot of repeated counting. Because a match must be exactly as long as the pattern, use a fixed-size sliding window equal to the pattern's length, and slide it one character at a time across the text. Maintain a running count of each letter currently inside the window alongside the pattern's own letter counts. As the window slides, adding the new rightmost character and removing the departing leftmost character keeps the running counts current in constant time, rather than recounting the whole window. The window is a match exactly when its counts equal the pattern's counts, which can be checked directly or tracked incrementally with a small "how many letters currently match" counter.

Solution

function checkInclusion(s1: string, s2: string): boolean {
  if (s1.length > s2.length) {
    return false;
  }

  const base = 'a'.charCodeAt(0);
  const patternCounts = new Array<number>(26).fill(0);
  const windowCounts = new Array<number>(26).fill(0);

  // build letter counts for the pattern and the first window of the same length
  for (let i = 0; i < s1.length; i++) {
    patternCounts[s1.charCodeAt(i) - base]++;
    windowCounts[s2.charCodeAt(i) - base]++;
  }

  let matches = 0;
  for (let i = 0; i < 26; i++) {
    if (patternCounts[i] === windowCounts[i]) {
      matches++;
    }
  }

  let left = 0;
  for (let right = s1.length; right < s2.length; right++) {
    if (matches === 26) {
      return true;
    }

    // slide the window: add the entering character on the right
    const enterIndex = s2.charCodeAt(right) - base;
    windowCounts[enterIndex]++;
    if (windowCounts[enterIndex] === patternCounts[enterIndex]) {
      matches++;
    } else if (windowCounts[enterIndex] === patternCounts[enterIndex] + 1) {
      matches--;
    }

    // and remove the leaving character on the left, keeping the window size fixed
    const leaveIndex = s2.charCodeAt(left) - base;
    windowCounts[leaveIndex]--;
    if (windowCounts[leaveIndex] === patternCounts[leaveIndex]) {
      matches++;
    } else if (windowCounts[leaveIndex] === patternCounts[leaveIndex] - 1) {
      matches--;
    }

    left++;
  }

  return matches === 26;
}

Complexity

  • Time: O(n). The window slides once across the text, with constant work per step since there are only 26 letters.
  • Space: O(1). Two fixed 26-entry count arrays, regardless of input length.

Watch out for

  • The window must stay exactly the pattern's length; every step both adds one character and removes one, rather than only expanding.
  • If the pattern is longer than the text, no match is possible and the answer is immediately false.
  • Comparing full count arrays at every step still runs in O(n) time since 26 is a constant, but an incremental match counter avoids that repeated work.

Pattern

This is the fixed-size sliding window with a frequency-equality check, distinct from the variable-size windows used elsewhere. The same window-of-exact-length idea powers "find all anagrams in a string" and other exact-length substring-matching problems.

Related questions