Start learning free

LESSON 397 OF 573 · SLIDING WINDOW

Permutation in String in Go: Sliding Window, O(n + m) Time

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

GO · SLIDING WINDOW

Permutation In String in Go, explained

Problem overview

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

So the question is whether s2 has a run of letters, exactly as long as s1, with the same letter counts as s1.

With s1 = "ab" and s2 = "eidbaooo" the answer is true: the run "ba" at indexes 3 and 4 is a permutation of "ab". With s2 = "eidboaoo" it is false: s2 has an a and a b, but never side by side. With s1 = "adc" and s2 = "dcda" it is true, because the last three letters, "cda", hold one a, one c and one d.

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

Approach: a window that keeps its counts up to date

The slow way is to take every substring of s2 of length m and count its letters from scratch. That costs O(n * m) time, too slow for strings of 100,000 letters.

The faster way slides a window of length m across s2 and updates the counts as it moves. When the window moves one step, one letter enters on the right and one letter leaves on the left, so only two counts change. No substring is ever counted again from scratch.

We don't compare two count arrays at every step, either. We keep one array, need, with 26 counts, one per letter. need[0] says how many more a's the window still needs, need[1] how many more b's, and so on. At the start, need holds the counts of s1. A letter that enters the window lowers its count, a letter that leaves raises it. A second number, missing, starts at m and counts how many letters of s1 the window still lacks. When missing is 0 and the window is exactly m letters long, it has all the letters of s1 with no room for others, so it is a permutation.

Here is a run on s1 = "ab", s2 = "eidbaooo". Each line shows the letter that just entered and the value of missing after the window is updated:

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

The e, i and d are not in s1, so missing stays at 2. The b brings it to 1. At last=4, the a arrives and the e leaves, and missing reaches 0: the window is "ba".

With s1 = "adc" and s2 = "dcda" the run is:

last=0 letter=d missing=2
last=1 letter=c missing=1
last=2 letter=d missing=1
last=3 letter=a missing=0

At last=2 the second d is extra, so missing stays 1. At last=3 the first d leaves and the a arrives: the window is "cda".

Step by step

Create need with make([]int, 26): 26 zeros, one per letter.
Count the letters of s1. A for loop with range over s1 gives each character as c; the index is dropped with _. Inside, need[c-'a']++ adds one. The letters a to z have consecutive codes, so c-'a' is 0 for a, 1 for b, and so on. A letter that appears twice in s1 is needed twice.
Set missing to len(s1): before the window holds anything, it lacks every letter.
Slide over s2. The loop variable last is the index of the window's right end. Each turn adds the letter at last.
Add the new letter. code is s2[last] - 'a', the letter's number from 0 to 25. If need[code] is above 0, s1 still needed this letter, so missing--. A count of 0 or less means the window already had all the copies s1 asks for, so this one is extra and missing stays. Then need[code]-- in every case. It can drop below 0, which means the window has more of that letter than s1.
Remove the old letter once the window is too long. When last >= len(s1), the window has m + 1 letters, so the first one, s2[last-len(s1)], leaves. Compute its number in oldCode and do need[oldCode]++, which undoes what its arrival did. If need[oldCode] is now above 0, the window lost a letter that s1 needs, so missing++. Otherwise it was a spare copy and nothing is lost.
Test the window. If missing == 0, return true. In the first turns the window is shorter than s1, so it can't hold all of its letters yet and missing can't be 0.
Return false after the loop. If s1 is longer than s2, missing never reaches 0, so this is the answer as well.

The solution in Go

func checkInclusion(s1 string, s2 string) bool {
    need := make([]int, 26)
    for _, c := range s1 {
        need[c-'a']++
    }
    missing := len(s1)
    for last := 0; last < len(s2); last++ {
        code := s2[last] - 'a'
        if need[code] > 0 {
            missing--
        }
        need[code]--
        if last >= len(s1) {
            oldCode := s2[last-len(s1)] - 'a'
            need[oldCode]++
            if need[oldCode] > 0 {
                missing++
            }
        }
        if missing == 0 {
            return true
        }
    }
    return false
}

Go details worth knowing

range over a string gives runes. In for _, c := range s1, c is a rune (an int32), the code of the character. Here the string is ASCII, so each character is one rune. For "ab", range yields index 0 with code 97 and index 1 with code 98.
Indexing a string gives a byte. s2[last] is a uint8 (byte), not a character. Subtracting 'a' gives another byte between 0 and 25 for a lowercase letter, which is a valid index for the slice need.
Two kinds of subtraction. c-'a' is an int32, and s2[last]-'a' is a byte. Both work as slice indexes. An index that is an integer type of any width is accepted.
len counts bytes. For lowercase English letters one byte is one letter, so len(s1) is the number of letters.
A slice of 26 ints plays the role of an array of counters. A map would work, too, but the slice is faster and its size doesn't depend on the input.

Complexity

Time: O(n + m). Counting s1 takes m steps. The window loop runs n times with constant work per turn: each letter of s2 enters the window once and leaves it once.

Space: O(1). The 26-element slice and a few integers don't grow with the input.

Edge cases and common mistakes

s1 longer than s2. No window of the right length exists. checkInclusion("abc", "ab") returns false.
Same length. The only window is s2 itself. checkInclusion("a", "a") returns true.
Repeated letters in s1. Having the right letters is not enough; the counts matter. checkInclusion("aab", "abcb") returns false, but checkInclusion("aab", "abab") returns true, thanks to the window "aba".
Letters in the wrong places. The letters of s1 may be spread out in s2 without making a permutation: checkInclusion("abc", "ccccbbbbaaaa") returns false. The substring has to be consecutive.
Counting the letters going out wrongly. The test need[oldCode] > 0 after the increment matters. Raising missing for every leaving letter would be wrong when the window held a spare copy of it.
Forgetting that the window must be exactly m long. Without the removal step, missing could reach 0 for a window longer than s1, which can hold extra letters.

Testing

"ab", "eidbaooo" gives true.
"ab", "eidboaoo" gives false.
"adc", "dcda" gives true.
"abc", "ab" gives false.
"a", "a" gives true.
"aab", "abab" gives true, and "aab", "abcb" gives false.

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

Start learning free