Start learning free

LESSON 393 OF 569 · SLIDING WINDOW

Permutation in String in JavaScript: 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

JAVASCRIPT · SLIDING WINDOW

Permutation In String in JavaScript, explained

Problem overview

The method checkInclusion(s1, s2) receives two strings of lowercase letters. It returns true when some substring of s2, a run of consecutive characters, is a permutation of s1: the same letters with the same counts, in any order. Otherwise it returns false.

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: the letters a and b are both present but never next to each other. With s1 = "adc" and s2 = "dcda" the answer is true, because the last three letters, "cda", hold one a, one c and one d.

The statement asks for O(n + m) time, where n is the length of s2 and m the length of s1, and constant extra space.

Approach: a window the length of s1 that slides over s2

A substring of s2 is a permutation of s1 exactly when it has the same length as s1 and the same count of every letter. So only windows of length s1.length matter.

The direct way counts the letters of every window from scratch, or sorts each window and compares it to the sorted s1. That costs about O(n · m) work, and it is slow when both strings are long. The faster way keeps the window's letter counts up to date as it slides: when the window moves one place to the right, one letter comes in and one letter leaves, and each of those changes a single count.

The lesson stores the counts as a deficit. The array need has 26 slots, one per letter, and starts as the counts of s1. A letter that enters the window lowers its slot, and a letter that leaves raises it. A positive slot means the window still lacks copies of that letter, and a negative one means it holds too many. Alongside it, missing counts how many letters of s1 the window still lacks in total. When missing is 0, the window holds every letter of s1 as often as s1 does, and since it is exactly as long as s1, there is no room for anything else.

Tracing s1 = "ab" and s2 = "eidbaooo", the window and missing after each turn of the loop are:

0 e window "e" missing 2
1 i window "ei" missing 2
2 d window "id" missing 2
3 b window "db" missing 1
4 a window "ba" missing 0

At index 4 the window is "ba", nothing is missing, and the function returns true. On s2 = "eidboaoo" the same trace ends with missing at 2 for the last window, "oo", and the function returns false.

Step by step

Create need as an array of 26 zeros, declared with let. Slot 0 is for a, slot 1 for b, and so on.
Loop over the characters of s1 with for...of. Before the window holds anything, it needs all of them.
Count each letter. c.charCodeAt(0) - 'a'.charCodeAt(0) turns a letter into 0 to 25, because the letter codes are consecutive. A letter that occurs twice in s1 is counted twice.
Set missing to s1.length. At the start the window lacks every letter.
Slide over s2 with last, the index of the letter that enters on the right. Each letter enters once and leaves once, so the whole loop is linear.
Compute the new letter's slot in code.
Update missing first. If need[code] is above 0, s1 still wanted this letter, so one fewer is missing. If it is 0 or less, the window already had all the copies it needs and this one is extra.
Then decrease need[code]. The window now holds one more of the letter, and the slot may go negative.
Check the window length. When last >= s1.length, the window has become one letter too long, so the letter at last - s1.length must leave.
Find the leaving letter's slot in oldCode.
Raise need[oldCode] to undo what that letter did when it came in.
Update missing again. If the slot is now above 0, the window lost a copy that s1 needs, so missing goes up. If the slot is 0 or less, the window had a spare copy and lost nothing needed.
Return true when missing === 0. In the first turns the window is shorter than s1, so it cannot reach 0 yet.
Return false after the loop. If s1 is longer than s2, missing never reaches 0, so this is also the right answer there.

The solution in JavaScript

class Solution {
    checkInclusion(s1, s2) {
        let need = 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;
    }
}

JavaScript details worth knowing:

Letters are strings, not numbers. JavaScript has no character type. for (const c of s1) gives one-character strings, and charCodeAt(0) returns the numeric code of the character at index 0 of that string. The same call on s2 with an index, s2.charCodeAt(last), reads the character at that position.
s2[i] against charCodeAt. s2[i] is a string such as "b", and subtracting two such strings would give NaN. The subtraction only works on the numeric codes.
A fixed array instead of an object. new Array(26).fill(0) is an array of 26 numbers. A plain array indexed by a small integer is simple, and the 26 slots never grow with the input.

Complexity

Time: O(n + m). Counting s1 takes m steps. The sliding loop runs n times and each turn does a constant number of operations: one letter in, at most one letter out, and one comparison.

Space: O(1). The array has 26 slots whatever the input length, plus a few integers.

Edge cases and common mistakes

s1 longer than s2. checkInclusion("abc", "ab") returns false. The window never gets long enough for missing to reach 0.
Same strings. checkInclusion("ab", "ab") returns true. The first window already matches, and the removal branch never runs.
Repeated letters. checkInclusion("aa", "aba") returns false, while checkInclusion("aa", "baab") returns true. Checking only that each letter appears in the window is not enough; the counts must match.
A match in the middle. checkInclusion("abc", "bbbca") returns true, from the window "bca". A letter that left the window must be counted out again, or this match would be missed.
Letters that are not in s1. checkInclusion("z", "abc") returns false. Their slots simply go negative and come back up when they leave.
Counting windows from scratch. Sorting or counting every window of a long s2 gives the right answers but takes far longer on large inputs. Updating the counts as the window slides is what makes the work linear.

Testing

s1 = "ab", s2 = "eidbaooo" gives true.
s1 = "ab", s2 = "eidboaoo" gives false.
s1 = "adc", s2 = "dcda" gives true.
s1 = "a", s2 = "a" gives true.
s1 = "abc", s2 = "ab" gives false.
s1 = "aa", s2 = "aba" gives false.
s1 = "aa", s2 = "baab" gives true.
A s1 of 50,000 a's followed by 50,000 b's against a s2 of 100,000 a's gives false, and the sliding window handles it quickly.

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

Start learning free