Permutation In String

The problem

You are given two strings of lowercase letters, pattern and text. Return true if some stretch of neighboring characters in text is a rearrangement of pattern, and false otherwise. A rearrangement has the same letters, each the same number of times, in any order. An empty pattern counts as found in any text.

What to write

function solve(pattern: string, text: string): boolean

Input
pattern = "ab"
text = "eidbaooo"

Output
true

Input
pattern = "ab"
text = "eidboaoo"

Output
false

Constraints

0–10,000 lowercase characters per string; empty pattern matches.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Both strings can hold 10,000 letters. Writing out every rearrangement of the pattern is hopeless: 10 different letters already have more than 3 million orders. Every rearrangement has the pattern's length, though, so only stretches of that one length can match.

2. Hint 2: Ask a smaller question

   Take the pattern "ab" and the first two letters of "eidbaooo", which are "ei". How can you tell that "ei" is not a rearrangement of "ab" without trying both orders? Now look at the next two letters, "id": what changed and what stayed?

3. Hint 3: Name the pattern

   Every candidate is a stretch of the text exactly as long as the pattern. Each one differs from the one before it by two letters: one comes in and one goes out. Compare letter counts instead of orders, and update the counts as the stretch moves along. This is a fixed-size sliding window. Read the lesson on fixed-size sliding window.

4. Hint 4: State the invariant

   Once the window is full, its counts always describe exactly the last m letters read, where m is the pattern's length. The window is a rearrangement of the pattern exactly when the two tables of counts are equal.

5. Hint 5: Sketch the pseudocode

   Count the pattern's letters; m is its length. For each position i of the text: add the letter at i to the window's counts. If i ≥ m, remove the letter at i - m. If i ≥ m - 1 and both counts are equal, return true. After the loop, return true only if the pattern is empty.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Count pattern characters and maintain counts in a window of the same length. Compare the fixed-size frequency arrays after each slide.

The slow way

Take every stretch of the text that is as long as the pattern, sort its letters and compare the result with the sorted pattern. It is correct, but each stretch is sorted from scratch, although it shares all but one letter with the stretch before it.

The insight

A rearrangement keeps the letter counts and changes only the order. So a stretch of the text, a window, matches exactly when its counts equal the pattern's. Moving the window one place to the right changes at most two counts: one for the letter that comes in, one for the letter that goes out.

Step by step

1. A pattern longer than the text cannot fit anywhere in it. A rearrangement is exactly as long as the pattern, and no stretch of the text is that long. The answer is known before any counting starts.
2. Count the pattern's letters and start an empty count for the window. With 26 possible letters, each count is a list of 26 numbers: slot 0 for a, slot 1 for b, and so on. The pattern's list never changes after this.
3. Add the next letter of the text to the window's counts. The window's right end moves one letter to the right, so that letter now belongs to the window and its slot goes up by one.
4. Once the window is longer than the pattern, drop its oldest letter. The window has to stay as long as the pattern. The letter that falls out is the one a full pattern's length behind the letter that came in.
5. A full window with the same counts as the pattern is a match. Equal counts mean the same letters, each the same number of times, which is what a rearrangement is. A window that is not full yet holds too few letters to match.
6. No window matched: the answer is false unless the pattern is empty. An empty pattern counts as found in any text. With an empty text the loop never runs and cannot say so, which is the one case this line turns into true.

The same numbered steps are the comments in each solution.

function solve(pattern, text) {
  // 1. A pattern longer than the text cannot fit anywhere in it
  if (pattern.length > text.length) return false;
  // 2. Count the pattern's letters and start an empty count for the window
  const a = Array(26).fill(0),
    b = Array(26).fill(0);
  // The character code of "a" is 97, so "a" lands in slot 0 and "z" in slot 25.
  for (const c of pattern) a[c.charCodeAt(0) - 97]++;
  for (let i = 0; i < text.length; i++) {
    // 3. Add the next letter of the text to the window's counts
    b[text.charCodeAt(i) - 97]++;
    // 4. Once the window is longer than the pattern, drop its oldest letter
    if (i >= pattern.length)
      b[text.charCodeAt(i - pattern.length) - 97]--;
    // 5. A full window with the same counts as the pattern is a match
    if (i >= pattern.length - 1 && a.every((n, j) => n === b[j]))
      return true;
  }
  // 6. No window matched: the answer is false unless the pattern is empty
  return pattern.length === 0;
}

function solve(pattern: string, text: string): boolean {
  // 1. A pattern longer than the text cannot fit anywhere in it
  if (pattern.length > text.length) return false;
  // 2. Count the pattern's letters and start an empty count for the window
  const a = Array(26).fill(0),
    b = Array(26).fill(0);
  // The character code of "a" is 97, so "a" lands in slot 0 and "z" in slot 25.
  for (const c of pattern) a[c.charCodeAt(0) - 97]++;
  for (let i = 0; i < text.length; i++) {
    // 3. Add the next letter of the text to the window's counts
    b[text.charCodeAt(i) - 97]++;
    // 4. Once the window is longer than the pattern, drop its oldest letter
    if (i >= pattern.length)
      b[text.charCodeAt(i - pattern.length) - 97]--;
    // 5. A full window with the same counts as the pattern is a match
    if (i >= pattern.length - 1 && a.every((n, j) => n === b[j]))
      return true;
  }
  // 6. No window matched: the answer is false unless the pattern is empty
  return pattern.length === 0;
}

def solve(pattern, text):
    # 1. A pattern longer than the text cannot fit anywhere in it
    size = len(pattern)
    if size > len(text):
        return False
    # 2. Count the pattern's letters and start an empty count for the window
    need = [0] * 26
    window = [0] * 26
    for char in pattern:
        need[ord(char) - ord("a")] += 1
    for i, char in enumerate(text):
        # 3. Add the next letter of the text to the window's counts
        window[ord(char) - ord("a")] += 1
        # 4. Once the window is longer than the pattern, drop its oldest letter
        if i >= size:
            window[ord(text[i - size]) - ord("a")] -= 1
        # 5. A full window with the same counts as the pattern is a match
        if i >= size - 1 and window == need:
            return True
    # 6. No window matched: the answer is false unless the pattern is empty
    return size == 0

Example 1, traced

Input
pattern = "ab"
text = "eidbaooo"

Output
true

Why it works

Once the window is full, its counts describe exactly the last m letters read, where m is the pattern's length. Each step keeps that true by adding the newest letter and removing the one that fell out. Two strings of equal length are rearrangements of each other exactly when their counts match, and every stretch of length m is the window at some step.

Time and space

Time O(n + m) for 26 letters, extra space O(1). Counting the pattern takes m steps. Each of the n letters of the text is added once and removed at most once. Each comparison checks 26 slots, a fixed number: O(n + m). The two lists hold 26 numbers each whatever the input, so the space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Compare counts, not sets of letters. "abb" holds the same letters as "aab" but is not a rearrangement of it: the pattern has two a's and one b.
• The letter to remove is the one a full pattern's length behind the new one. One position off in either direction and the counts describe the wrong letters: one place too far right, and example 1 returns false.
• In JavaScript, comparing two arrays with === asks whether they are the same array, not whether they hold the same numbers, so it is always false here. Compare them slot by slot. Python's == does compare the contents.

Pattern

Fixed-size sliding window. Builds on Valid Anagram and Longest Substring Without Repeating Characters.

Keep going