Typorithm · medium

Permutation in String

permutation-in-stringsliding-windowfixed-windowneed-maprequired-counter

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Permutation in String

Sliding Window

Slide a fixed window the size of the pattern; a required counter hits 0 exactly when the window is a permutation.

A permutation of s1 inside s2 is a substring of length s1.length with matching character counts.

Build a need-map of required counts and a required counter of distinct characters left to satisfy.

Slide a fixed-width window; when required reaches 0, the counts match exactly and a permutation is found.

Window width is fixed at s1.length.

need-map counts down to zero per char.

required === 0 means a match.

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

  const need = new Map();
  for (const ch of s1) {
    need.set(ch, (need.get(ch) ?? 0) + 1);
  }

  let required = need.size;
  let left = 0;

  for (let right = 0; right < s2.length; right += 1) {
    const rc = s2[right];
    if (need.has(rc)) {
      need.set(rc, need.get(rc) - 1);
      if (need.get(rc) === 0) {
        required -= 1;
      }
    }

    if (right - left + 1 > s1.length) {
      const lc = s2[left];
      if (need.has(lc)) {
        if (need.get(lc) === 0) {
          required += 1;
        }
        need.set(lc, need.get(lc) + 1);
      }
      left += 1;
    }

    if (required === 0) {
      return true;
    }
  }

  return false;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Required counts

Count how many of each character the pattern needs.

need.set(ch, (need.get(ch) ?? 0) + 1)

2. Distinct targets

required falls to 0 when every needed count is met.

let required = need.size

3. Count satisfied

A character's count reaching exactly 0 satisfies it.

if (need.get(rc) === 0) {
        required -= 1;
      }

4. Fixed width

Slide a window of exactly the pattern's length.

if (right - left + 1 > s1.length) {

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.