Start learning free

LESSON 397 OF 573 · SLIDING WINDOW

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

KOTLIN · SLIDING WINDOW

Permutation In String in Kotlin, explained

Problem overview

Given two strings of lowercase letters, s1 and s2, the method returns true when s2 contains a permutation of s1 as a substring. A permutation uses the same letters as s1, each as many times, in any order. A substring is a run of consecutive characters. So the question is whether some run of s2, exactly as long as s1, holds every letter as many times as s1 does.

For s1 = "ab" and s2 = "eidbaooo" the answer is true, because s2 contains "ba" at indexes 3 and 4. For s2 = "eidboaoo" it is false: there is an a and a b, but never next to each other. For s1 = "adc" and s2 = "dcda" the answer is true because of the last three letters, "cda".

Approach

The direct method takes every substring of s2 with the length of s1, counts its letters and compares them with the letters of s1. With strings of 100,000 letters that is O(n · m) work, too slow.

The window method avoids recounting. The window is a run of s2 exactly as long as s1. When it slides one place to the right, one letter enters on the right and one leaves on the left, so a count array can be updated in constant time. The lesson keeps one array of 26 counts, need, with this meaning: need[x] is how many more copies of letter x the window still needs. A negative value means the window holds more of that letter than s1 has. Next to it, a counter missing says how many letters of s1 the window still lacks. When missing is 0, the window holds every letter of s1 as many times as s1 has it, and since the window is exactly as long as s1, it has no room for anything else: it is a permutation.

Each letter of s2 enters the window once and leaves it once, so the time is O(n + m), and the 26 counts are constant extra space.

Step by step

The counts. Create val need = IntArray(26), 26 zeros. A val array can still change its elements.
Count s1. Loop for (c in s1) and do need[c - 'a']++. Subtracting two Chars gives an Int, and 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.
The missing counter. Start var missing = s1.length: before the window holds anything, every letter is missing.
Slide. Loop last over s2.indices. Each turn, the letter at index last enters the window on its right end.
The entering letter. Store its number in val code = s2[last] - 'a'. If need[code] > 0, s1 still needed this letter, so missing--. If the count is 0 or less, the window already has all the copies s1 asks for, so this one is extra and missing stays.
Update the count. Do need[code]-- either way: the window holds one more of this letter.
Drop the leaving letter. When last >= s1.length, the window has become one letter too long, so the first letter, s2[last - s1.length], must leave. Store its number in oldCode, do need[oldCode]++, and if the count is now above 0 the window lost a letter that s1 needs, so missing++.
Test. If missing == 0, return true.
No window matched. After the loop, return false. This also covers the case where s1 is longer than s2: missing can never reach 0.

The solution in Kotlin

class Solution {
    fun checkInclusion(s1: String, s2: String): Boolean {
        val need = IntArray(26)
        for (c in s1) {
            need[c - 'a']++
        }
        var missing = s1.length
        for (last in s2.indices) {
            val code = s2[last] - 'a'
            if (need[code] > 0) missing--
            need[code]--
            if (last >= s1.length) {
                val oldCode = s2[last - s1.length] - 'a'
                need[oldCode]++
                if (need[oldCode] > 0) missing++
            }
            if (missing == 0) return true
        }
        return false
    }
}

Kotlin details:

for (c in s1) goes over the characters of a String directly, and s2.indices is the range 0 until s2.length.
'd' - 'a' is an Int (it is 3). A Char minus a Char gives an Int, which is what an array index needs, so no .code call is required.
need[code]-- works on an array element: it reads, subtracts 1 and stores back.
One-line if (...) missing-- without braces is valid Kotlin when the body is a single statement.
The function returns from inside the loop. Reaching the last line means every window failed.

A trace

With s1 = "ab" and s2 = "eidbaooo", this is the state after each turn (a and b are need[0] and need[1]), until the method stops:

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

Letters that s1 doesn't contain, like e, i and d, only push their own counts below zero and are later undone when they leave. At last=4 the window is "ba", missing is 0, and the method returns true.

A second trace, with a repeated letter: s1 = "aab" and s2 = "abab".

last=0 letter=a a=1 b=1 missing=2
last=1 letter=b a=1 b=0 missing=1
last=2 letter=a a=0 b=0 missing=0

Here s1 has two a's, so need[0] starts at 2, and the window "aba" is a permutation of "aab".

Complexity

Time: O(n + m), where n is the length of s2 and m the length of s1. Counting s1 takes m steps, and the window loop runs n turns of constant work.

Space: O(1). The array has 26 entries however long the strings are.

Edge cases and common mistakes

s1 longer than s2. checkInclusion("abc", "ab") returns false. The window never gets long enough, so missing stays above 0.
Equal single letters. checkInclusion("a", "a") returns true.
Repeated letters. Counts, not just sets, are needed. "aab" in "abbaa" is found (the run "baa"), and "hello" is not found in "ooolleoooleh".
Letters from outside s1. They may enter and leave the window freely; they push their counts below 0, and the window can't reach missing == 0 while one of them is inside, because the window is only as long as s1.
Changing missing for spare copies. Only a letter that s1 still needs (a count above 0 before it enters, or after it leaves) changes missing. Adjusting it on every enter or leave makes it wrong as soon as a letter is repeated or comes from outside s1.

Testing

These calls were run against the solution above:

`s1`	`s2`	Result
`"ab"`	`"eidbaooo"`	`true`
`"ab"`	`"eidboaoo"`	`false`
`"adc"`	`"dcda"`	`true`
`"abc"`	`"ab"`	`false`
`"a"`	`"a"`	`true`
`"aab"`	`"abbaa"`	`true`
`"hello"`	`"ooolleoooleh"`	`false`

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

Start learning free