Start learning free

LESSON 397 OF 573 · SLIDING WINDOW

Permutation in String in TypeScript: O(n + m) Sliding Window

Practice O(n) Read the full explanation

You are given two strings s1 and s2 made of lowercase English letters. Return true if s2 contains a permutation of s1 as a substring, and false otherwise.

A permutation of s1 is a string made of the same letters as s1, each one as many times, in any order: "abb", "bab" and "bba" are the permutations of "abb". A substring is a run of consecutive characters of s2.

So the question is: does s2 have a run of consecutive letters, exactly as long as s1, that holds every letter as many times as s1 does?

Your solution returns a boolean, and the tests print 1 for true and 0 for false.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains "ba", at indexes 3 and 4, and "ba" is a permutation of "ab".

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Explanation: s2 has an a and a b, but never next to each other: every run of two letters misses one of them.

Example 3:

Input: s1 = "adc", s2 = "dcda"
Output: true
Explanation: The last three letters, "cda", hold one a, one c and one d, just like "adc". The first three, "dcd", have two d's and no a.

Constraints:

1 <= s1.length, s2.length <= 10⁵
s1 and s2 are made of lowercase English letters only (a to z).

Note:

Your algorithm should run in O(n + m) time, where n is the length of s2 and m the length of s1, and use O(1) extra space: one count for each of the 26 letters. Checking every substring of s2 on its own takes O(n · m) time, too slow for the largest tests.

STEP 1 OF 14

Guided

Ctrl + Enter to check

TYPESCRIPT · SLIDING WINDOW

Permutation In String in TypeScript, explained

Problem overview

The method checkInclusion receives two strings of lowercase letters, s1 and s2. It returns true when s2 contains a permutation of s1 as a substring, and false otherwise. A permutation of s1 uses the same letters, each one as many times, in any order: "abb", "bab" and "bba" are the permutations of "abb". A substring is a run of consecutive characters.

So the question is whether s2 has a run of letters, exactly as long as s1, that holds every letter as many times as s1 does. With s1 = "ab" and s2 = "eidbaooo" the answer is true, because "ba" sits at indexes 3 and 4. With s2 = "eidboaoo" the answer is false: it has an a and a b, but never next to each other. With s1 = "adc" and s2 = "dcda" the answer is true, thanks to the last three letters, "cda".

Approach: slide a window and keep a letter count

The direct way sorts or counts every substring of s2 of the right length and compares it with s1. With strings of up to 100,000 letters that takes O(n · m) time, too slow.

The faster idea uses a window: a run of s2 exactly as long as s1, sliding one letter to the right at a time. When the window moves, one letter enters on the right and one leaves on the left, so everything else stays the same. Instead of counting the window again from scratch, you update a count for the two letters that changed.

The count is an array need with 26 slots, one per letter. It starts out holding what s1 needs: need[0] is the number of a's, need[1] the number of b's, and so on. When a letter enters the window, its slot goes down by one, because the window holds one more of it. When a letter leaves, its slot goes up by one. A slot at 0 means the window holds exactly as many of that letter as s1 has. A positive slot means the window still lacks some copies. A negative slot means the window has too many.

Checking all 26 slots on every turn would cost 26 steps per letter, which is a constant and still fine. The lesson goes one better with a single number, missing: how many letters of s1 the window still lacks. It starts at s1.length. A letter entering the window lowers it only if s1 still needed that letter (its slot is above 0). A letter leaving raises it only if the window loses a copy that s1 needs. When missing reaches 0 and the window is exactly as long as s1, the window holds all the letters of s1 and nothing else, so it is a permutation.

Tracing s1 = "ab" and s2 = "eidbaooo", the value of missing after each letter comes in is:

last 0 e missing 2
last 1 i missing 2
last 2 d missing 2
last 3 b missing 1
last 4 a missing 0
found

Before the window is full, the letters e, i and d come in. They are not in s1, so missing stays at 2, and once the window is full they leave again. The b brings it to 1 and the a to 0, so the method returns true at index 4.

Step by step

Create need as a number[] of 26 zeros, declared with let, using new Array(26).fill(0).
Count the letters of s1 with a for...of loop over its characters.
Add 1 to the letter's slot. c.charCodeAt(0) - 'a'.charCodeAt(0) turns a letter into a number from 0 to 25, because the codes of a to z are consecutive.
Start missing at s1.length: before the window holds anything, it lacks every letter.
Loop over s2 with last as the index of the letter entering on the right.
Find the new letter's slot in code.
If need[code] is above 0, lower missing. s1 still wanted this letter. If the count is 0 or less, the window already had enough of it, and this copy is extra.
Lower need[code] by one in every case. The count may go below 0 when the window holds more of a letter than s1 has.
Check whether the window got too long: last >= s1.length.
Find the leaving letter's slot in oldCode. It is the letter s1.length places to the left of the new one.
Raise need[oldCode] by one, which undoes what the letter did when it came in.
If need[oldCode] is now above 0, raise missing. The window lost a copy that s1 needs. If the count is still 0 or less, the window had a spare copy and lost nothing.
If missing === 0, return true. Early in the loop the window is shorter than s1 and can't hold all its letters yet, so this never fires too soon.
Return false after the loop. This also covers the case where s1 is longer than s2: missing can never reach 0.

The solution in TypeScript

class Solution {
    checkInclusion(s1: string, s2: string): boolean {
        let need: number[] = new Array(26).fill(0);
        for (const c of s1) {
            need[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        let missing = s1.length;
        for (let last = 0; last < s2.length; last++) {
            let code = s2.charCodeAt(last) - 'a'.charCodeAt(0);
            if (need[code] > 0) missing--;
            need[code]--;
            if (last >= s1.length) {
                let oldCode = s2.charCodeAt(last - s1.length) - 'a'.charCodeAt(0);
                need[oldCode]++;
                if (need[oldCode] > 0) missing++;
            }
            if (missing === 0) return true;
        }
        return false;
    }
}

Details that matter in TypeScript:

Strings are not indexed as numbers. A letter's number comes from charCodeAt. 'a'.charCodeAt(0) is 97 and 'z'.charCodeAt(0) - 'a'.charCodeAt(0) is 25, so the codes of the 26 letters map to the slots 0 to 25.
for (const c of s1) goes over a string one character at a time. Each c is a one-letter string, so you call charCodeAt(0) on it. The lesson's input is limited to lowercase a to z, so no other character can produce a slot outside 0 to 25.
new Array(26).fill(0) creates 26 empty places and fills them with the number 0. With numbers, sharing is harmless: unlike objects or sets, a number is copied when stored.
++ and -- on an array element. need[code]-- reads the slot, subtracts one and writes it back, so it can take the slot below zero, which is how "the window has too many" is recorded.
Annotations are erased. number[] on need is only for the compiler. At run time need is a plain JavaScript array.
missing === 0 compares without converting types. It is the usual way to test a number against a literal in TypeScript.

Complexity

Time: O(n + m), where n is the length of s2 and m the length of s1. Counting the letters of s1 takes m steps. The sliding loop runs n times, and each letter of s2 enters the window once and leaves it at most once, each time with constant work.

Space: O(1). The array need always has 26 slots, whatever the length of the strings.

Edge cases and common mistakes

s1 longer than s2. "abc" with "ab" gives false. The window never reaches the length of s1 without running out of letters.
Equal length. "a" with "a" gives true at the first letter.
Repeated letters. "aab" with "abaa" gives true, because "baa" has two a's and one b. "aab" with "abxab" gives false: the a's and the b are never in a run of three.
Counting presence instead of amounts. A window with "dcd" has the letters d and c, but two d's and no a, so it is not a permutation of "adc". The counts have to match, not just the set of letters.
Letting missing go up for any leaving letter. Only a letter whose slot rises above 0 means the window lost something s1 needs. After the window has slid past a surplus letter, missing must stay the same.
Checking before the window is full. The check missing === 0 sits after the removal step. While the window is shorter than s1, missing is still above 0, so it can't fire.

Testing

"ab", "eidbaooo" gives true.
"ab", "eidboaoo" gives false.
"adc", "dcda" gives true.
"abc", "ab" gives false.
"a", "a" gives true.
"aab", "abaa" gives true.
"aab", "abxab" gives false.

Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free