Skip to content

Volume ITechnology

4.6.4 — Permutation in String ​

LeetCode 567 · Medium

The problem ​

You are given two strings, s1 and s2. Return true if some permutation of s1 appears inside s2 as a substring. A permutation of a word is any rearrangement of all its letters. The permutations of "ab" are "ab" and "ba".

s1 = "ab", s2 = "eidbaooo"   →  true     ("ba" appears at positions 3 and 4)
s1 = "ab", s2 = "eidboaoo"   →  false    (the b and a are never side by side)

Both strings use only lowercase English letters, and each has between 1 and 10,000 of them.

What the problem is really asking ​

A permutation of s1 uses exactly the same letters as s1, the same number of times. From 4.4.2 Valid Anagram, you know that means the same letter counts. A permutation also has exactly the same length as s1.

So the question becomes: is there a stretch of s2, exactly as long as s1, whose letter counts match the counts of s1?

The brute force, and where it wastes work ​

For each starting position in s2, take the stretch of length len(s1), count its letters, and compare with s1's counts.

python
def checkInclusion(s1, s2):
    m = len(s1)
    target = sorted(s1)
    for i in range(len(s2) - m + 1):
        if sorted(s2[i:i + m]) == target:
            return True
    return False

There are about n starting positions, and each one rebuilds and sorts a stretch of m letters. That is O(n \cdot m \log m).

The waste in one sentence: two neighbouring stretches share all but two letters, one leaving on the left and one entering on the right, yet the brute force recounts the whole stretch from scratch.

The idea ​

This is a fixed-size window, which is simpler than the windows on the last two pages. There is no rule for shrinking and no while loop. The window is always exactly len(s1) long.

Think of a cardboard stencil with a slot cut in it, exactly as long as s1. Lay it over the start of s2 and count the letters you can see through the slot. If they match s1's counts, you are done. If not, slide the stencil one letter to the right. One letter is covered up on the left, and one new letter appears on the right. You only adjust those two counts.

We keep two lists of 26 counts, one for s1 and one for the window, and compare them after each slide.

The solution ​

python
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):                                      # (1)
            return False

        need = [0] * 26                                            # (2)
        window = [0] * 26
        for i in range(len(s1)):                                   # (3)
            need[ord(s1[i]) - ord('a')] += 1
            window[ord(s2[i]) - ord('a')] += 1

        if need == window:                                         # (4)
            return True

        for right in range(len(s1), len(s2)):                      # (5)
            window[ord(s2[right]) - ord('a')] += 1                 # (6)
            window[ord(s2[right - len(s1)]) - ord('a')] -= 1       # (7)
            if need == window:                                     # (8)
                return True

        return False                                               # (9)
ts
function checkInclusion(s1: string, s2: string): boolean {
  if (s1.length > s2.length) return false;                         // (1)
  const a = 'a'.charCodeAt(0);

  const need = new Array(26).fill(0);                              // (2)
  const window = new Array(26).fill(0);
  for (let i = 0; i < s1.length; i++) {                            // (3)
    need[s1.charCodeAt(i) - a]++;
    window[s2.charCodeAt(i) - a]++;
  }

  const same = () => need.every((v, i) => v === window[i]);
  if (same()) return true;                                         // (4)

  for (let right = s1.length; right < s2.length; right++) {        // (5)
    window[s2.charCodeAt(right) - a]++;                            // (6)
    window[s2.charCodeAt(right - s1.length) - a]--;                // (7)
    if (same()) return true;                                       // (8)
  }

  return false;                                                    // (9)
}

Line by line ​

(1) s1 longer than s2. Then no stretch of s2 is long enough, so the answer is false. This line also protects line (3), which reads s2[i] for every i up to len(s1). Without it, that would run past the end of a short s2.

(2) Two lists of 26 counts. need will hold the letter counts of s1. window will hold the counts of the current stretch of s2.

(3) Fill both lists. One loop counts all of s1, and also counts the first len(s1) letters of s2. That second part is the window in its starting position. ord(c) - ord('a') turns a letter into a slot from 0 to 25, as on the Valid Anagram page.

(4) Check the first window. In Python, == on two lists compares them slot by slot. In TypeScript, == on arrays only checks whether they are the very same object, so we write a small helper, same, that compares the slots.

(5) Slide the window. right is the position of the letter that enters the window on this step. It starts at len(s1), the first letter after the starting window.

(6) Count the entering letter.

(7) Uncount the leaving letter. The window always holds exactly len(s1) letters, ending at right. So the letter that just fell off the left side is at right - len(s1). Check it on the first slide. When right is len(s1), the leaving letter is at position 0, the very first letter. That is right: the window has just slid past it. Getting this position off by one is the most common bug on this page.

(8) Compare. If the counts match, this window is a permutation of s1.

(9) No window matched.

Trace ​

Take s1 = "ab" and s2 = "eidbaooo". need has a:1, b:1. The window is 2 letters long. We only show the non-zero counts.

StepWindowLetter inLetter outWindow countsMatch?
start"ei"——e:1, i:1no
right=2"id"dei:1, d:1no
right=3"db"bid:1, b:1no
right=4"ba"adb:1, a:1yes → true

Complexity, derived ​

Let m be the length of s1 and n the length of s2.

Time. Line (3) runs m times. The slide loop runs n - m times. Each slide does two count updates and one comparison of 26 slots. Comparing 26 slots is a fixed amount of work, because 26 never changes, so each slide is constant work. The total is O(m + n).

Space. Two lists of 26 numbers, 52 numbers in all, whatever the input size. That is O(1).

A faster step: count how many letters match ​

Comparing 26 slots on every slide is constant, but not free. You can make each slide truly one or two steps by keeping a number matches: how many of the 26 letters currently have equal counts in need and window. The answer is true when matches == 26.

On each slide only two slots change, so only those two can switch between "equal" and "not equal". After changing a slot, check: did it just become equal (add 1 to matches)? Or did it just stop being equal (subtract 1)?

The bookkeeping is fiddly. In an interview, the 26-slot comparison is the better first answer. It is obviously correct and still linear. Mentioning matches afterwards shows you know the refinement exists.

Edge cases ​

  • s1 longer than s2. Line (1) returns false.
  • The match is at the very end of s2. The last slide updates the window, line (8) finds the match, and returns true.
  • Repeated letters, like s1 = "aab". The counts handle two as naturally.
  • s1 and s2 the same length. No slides happen. Only line (4) decides.

Variations you will meet ​

  • Find All Anagrams in a String. The same code, but instead of returning on the first match, collect the starting position of every matching window. The start of the window ending at right is right - len(s1) + 1. This is a good self-test.
  • Minimum Window Substring. Counts again, but now the window size is not fixed, and you want the shortest window that contains all of s1's letters. That is the next page, 4.6.5, and it is much harder.

The general lesson: a fixed-size window has no while loop. If you know the window's length in advance, you just slide it. If the length is the thing you are trying to make biggest or smallest, you grow and shrink it. Decide which kind you have before you write any code.

What the interviewer will push on ​

"Why is comparing 26 slots still constant time?" Because 26 is fixed by the problem. It does not grow with the input.

"Can you avoid the 26 comparisons per step?" Describe the matches counter. You do not need to write it unless asked.

"What if the strings could hold any Unicode character?" The lists become maps, and comparing them is no longer constant. Then the matches counter becomes worth writing.

"Which letter leaves the window, exactly?" The one at right - len(s1). Check it on the first slide.

One thing to volunteer: say that this is Valid Anagram run on every window, and the only new idea is updating the counts by two letters instead of recounting.

Next: 4.6.5 Minimum Window Substring. The hardest window problem, where you want the shortest valid window instead of the longest.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet