Start learning free

LESSON 397 OF 573 · SLIDING WINDOW

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

SCALA · SLIDING WINDOW

Permutation In String in Scala, 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 uses the same letters as s1, each as many times, in any order. A substring is a run of consecutive characters of s2.

So the real question is: does s2 have 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 run "ba" at indexes 3 and 4 qualifies, so the answer is true. With s2 = "eidboaoo" the letters a and b are never side by side, so the answer is false. With s1 = "adc" and s2 = "dcda", the last three letters, "cda", hold one a, one c and one d, so the answer is true.

Approach: a window with a running shortfall

The slow idea sorts or counts every substring of s2 of length s1.length from scratch. That costs O(n * m) time, where n is the length of s2 and m the length of s1, which is too slow for strings of 100,000 letters.

The faster idea slides a window of exactly s1.length letters along s2 and updates its description instead of rebuilding it. When the window moves one step, one letter enters on the right and one leaves on the left. Only two counts change.

The description is an array need of 26 counters, one per letter. At first need holds the letters of s1: need(0) is how many a's the window still needs, need(1) how many b's, and so on. Each letter that enters the window lowers its counter. A counter that goes below zero means the window holds more of that letter than s1 has.

Checking all 26 counters at every step would add a factor of 26. Instead, a single number, missing, tracks how many letters of s1 the window still lacks. It starts at s1.length. A letter entering the window reduces missing only when s1 still needed it, that is, when its counter was above zero before the letter arrived. A letter leaving the window raises missing only when it was one the window needed to keep, that is, when its counter climbs back above zero. When missing is 0, the window holds every letter of s1, and since the window is exactly as long as s1, it can't hold anything else: it is a permutation.

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

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

At index 4 the window is "ba" and missing is 0, so the method returns true. For s1 = "adc" and s2 = "dcda", missing goes 2, 1, 1, 0: the second d adds nothing, because the only d that s1 needs is already in the window, and the final a completes it.

Step by step

Create the counters. Array.fill(26)(0) gives 26 zeros in a val. The array's elements can still change.
Loop over the letters of s1 with for (c <- s1). A String can be used as a collection of its characters.
Count each letter with need(c - 'a') += 1. Subtracting two Chars gives an Int, and a to z have consecutive codes, so c - 'a' is 0 for a, 1 for b and so on. A letter twice in s1 is needed twice.
Set missing to s1.length in a var: before the window holds anything, it lacks every letter.
Slide the window with for (last <- s2.indices). On each turn, last is the index of the letter entering on the right. Every letter of s2 enters once and leaves once, so the loop is O(n).
Find the new letter's number with s2(last) - 'a', in a val named code.
Update missing first. If need(code) > 0, the window just got a letter s1 still needed: subtract 1 from missing. A counter of 0 or less means the window already had all the copies s1 asks for, so this one is extra.
Then update the counter: need(code) -= 1. It may drop below 0, which marks surplus.
Drop the oldest letter when the window is too long. After a letter comes in, the window is one longer than s1 if last >= s1.length. Then the letter at index last - s1.length must leave.
Undo its effect: compute its number as oldCode and add 1 to need(oldCode).
Update missing for the leaver. If need(oldCode) is now above 0, the window lost a letter s1 needs, so add 1 to missing. If it is still 0 or less, the window had a spare copy and lost nothing needed.
Test for a match. If missing == 0, return true right away. In the first turns the window is shorter than s1, so it can't be complete yet.
Return false after the loop. No window matched. This also covers a s1 longer than s2, where missing never reaches 0.

The solution in Scala

class Solution {
    def checkInclusion(s1: String, s2: String): Boolean = {
        val need = Array.fill(26)(0)
        for (c <- s1) {
            need(c - 'a') += 1
        }
        var missing = s1.length
        for (last <- s2.indices) {
            val code = s2(last) - 'a'
            if (need(code) > 0) missing -= 1
            need(code) -= 1
            if (last >= s1.length) {
                val oldCode = s2(last - s1.length) - 'a'
                need(oldCode) += 1
                if (need(oldCode) > 0) missing += 1
            }
            if (missing == 0) return true
        }
        false
    }
}

The Scala details worth a closer look:

Strings behave like sequences. for (c <- s1) visits each Char, s2(last) reads the character at an index (with parentheses, not square brackets), and s2.indices is the range 0 until s2.length.
Char minus Char is an Int. 'c' - 'a' is 2 and 'z' - 'a' is 25. That is why the result can index need directly.
need(code) -= 1 on an array element. It is shorthand for need(code) = need(code) - 1. The array is a val, but its contents are mutable.
One-line if without braces. if (need(code) > 0) missing -= 1 controls exactly one statement. It is fine for such short bodies, but adding a second line under it would run unconditionally.
The order of the two updates matters. missing is adjusted before the counter changes when a letter enters, and after it changes when a letter leaves. In both cases the test asks about the counter's value on the "needed" side of zero.
return inside a for. The loop body is a closure, and Scala 3.5 prints the warning "Non local returns are no longer supported" for return true there. The code still compiles and works. The suggested alternative is scala.util.boundary with boundary.break.
The final false needs no return. The last expression of the method is its value.

Complexity

Time: O(n + m). Counting the letters of s1 takes m steps. The window loop runs n times with a constant amount of work in each, because only two counters change. No substring is ever recounted from scratch.

Space: O(1). The only extra memory is the array of 26 counters and a few integers, whatever the length of the strings.

Edge cases and common mistakes

s1 longer than s2. "abc" in "ab" gives false: the window can never hold all of s1.
Single letters. "a" in "a" gives true, and "a" in "b" gives false.
Repeated letters. "aab" in "baa" and in "abab" are both true. A permutation needs the same number of each letter, not just the same letters. In "hello" against "ooolleoooleh" every letter shows up somewhere, but no run of five letters holds exactly h, e, l, l and o, so the answer is false.
Checking letters but not counts. The string "bbbca" holds the letters a, b and c, but the runs "bbb" and "bbc" are not permutations of "abc". Only "bca" is, and the counters accept exactly that run: a window with a surplus letter never reaches missing == 0.
Forgetting to remove the oldest letter. Without the last >= s1.length block the window grows to cover the whole prefix of s2, and it would report true on a string that contains the letters spread out.
Getting the leaving index wrong. After the letter at last comes in, the window covers last - s1.length to last. The leaver is at last - s1.length.

Testing

s1 = "ab", s2 = "eidbaooo" gives true.
s1 = "ab", s2 = "eidboaoo" gives false.
s1 = "adc", s2 = "dcda" gives true.
s1 = "abc", s2 = "ab" gives false.
s1 = "aab", s2 = "baa" gives true.
s1 = "abc", s2 = "bbbca" gives true.
s1 = "hello", s2 = "ooolleoooleh" gives false.

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

Start learning free