Adjacent Spice Jars

Mediumsliding windowAlso known as Permutation in String

A busy restaurant kitchen has one long shelf of spice jars. Each jar is labelled with one letter: c for cumin, p for paprika, s for salt, and so on. The shelf, read left to right, is a string like "sppcsx".

A recipe card lists the jars it needs, for example "cps". The chef wants to grab everything with one sweep of the arm: a block of jars standing side by side that holds exactly the recipe's jars, in any order, with nothing extra. Is there such a block on the shelf?

Your task

Write hasSpiceBlock(shelf, recipe). Return true if some run of recipe.length consecutive characters in shelf contains exactly the same letters as recipe, each the same number of times, in any order. Otherwise return false.

If recipe is longer than shelf, return false.

hasSpiceBlock(shelf: string, recipe: string) → bool

Examples

Example 1

Input

shelf = "sppcsx"
recipe = "cps"

Output

true

Why

The first two blocks, spp and ppc, each have two p's. The block at positions 2 to 4, pcs, has one c, one p and one s: exactly the recipe, in a different order. Return true.

Example 2

Input

shelf = "paspca"
recipe = "aap"

Output

false

Why

The recipe needs two a's and one p. The 3-jar blocks are pas, asp, spc, pca. None has two a's, even though the shelf has two a's in total. They are just too far apart.

Constraints

1 ≤ recipe.length ≤ 1,000
0 ≤ shelf.length ≤ 10,000
shelf and recipe contain lowercase letters a-z only.

Start with brute force

For every starting position, take the next m jars, sort them, and compare with the sorted recipe.

Sorting each block costs about m log m. With a 10,000-jar shelf and a 1,000-letter recipe that is roughly 9,000 blocks × 10,000 steps: around 90 million operations. All that recounting is wasted, because each block differs from the previous one by just two jars.

Hints

0 of 4 shown

Hint 1
The block must have exactly recipe.length jars. In the first example that is 3. How many different 3-jar blocks does the shelf have, and how could you describe each one so the order does not matter?
Hint 2
Describe a block by how many jars of each letter it has. A block matches when its counts equal the recipe's counts.
Hint 3
Neighbouring blocks share all their jars but one at each end. When the block slides one step right, exactly one jar enters and one jar leaves, so you can update the counts instead of recounting.
Hint 4
Count the recipe's letters. Count the first m jars of the shelf (m = recipe length). Then slide: add the jar at i, remove the jar at i - m, and compare the two sets of counts after every step. With 26 letters, each comparison is a fixed amount of work.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

"Same jars in any order" means "same count of each letter". So describe the recipe by its letter counts, and keep the letter counts of a window of exactly m jars as it slides along the shelf.

Trace shelf "sppcsx" and recipe "cps", which needs c 1, p 1, s 1:

First window spp: s 1, p 2. No c and one p too many. No match.
Slide: c enters on the right, s leaves on the left. Window ppc: p 2, c 1. No match.
Slide: s enters, p leaves. Window pcs: p 1, c 1, s 1. Same as the recipe. Return true.

Each slide changes exactly two counts, and comparing two arrays of 26 counts is a fixed amount of work, however long the recipe is.

Reference solution

function hasSpiceBlock(shelf, recipe) {
  const m = recipe.length;
  if (m > shelf.length) return false;
  const idx = (ch) => ch.charCodeAt(0) - 97;
  const need = new Array(26).fill(0);
  const have = new Array(26).fill(0);
  for (let i = 0; i < m; i++) {
    need[idx(recipe[i])]++;
    have[idx(shelf[i])]++;
  }
  const same = () => need.every((n, k) => n === have[k]);
  if (same()) return true;
  for (let i = m; i < shelf.length; i++) {
    have[idx(shelf[i])]++;      // jar entering on the right
    have[idx(shelf[i - m])]--;  // jar leaving on the left
    if (same()) return true;
  }
  return false;
}

def has_spice_block(shelf, recipe):
    m = len(recipe)
    if m > len(shelf):
        return False
    need = [0] * 26
    have = [0] * 26
    for i in range(m):
        need[ord(recipe[i]) - 97] += 1
        have[ord(shelf[i]) - 97] += 1
    if need == have:
        return True
    for i in range(m, len(shelf)):
        have[ord(shelf[i]) - 97] += 1      # jar entering on the right
        have[ord(shelf[i - m]) - 97] -= 1  # jar leaving on the left
        if need == have:
            return True
    return False

TimeO(n)One pass over the shelf, and each step updates two counts and compares 26 numbers.

SpaceO(1)Two arrays of 26 counts, whatever the input size.

Learn the idea: Sliding Window Hash Tables Strings

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code