Start learning free

LESSON 398 OF 574 · SLIDING WINDOW

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

Guided

Ctrl + Enter to check

SWIFT · SLIDING WINDOW

Permutation In String in Swift, explained

Problem overview

The method checkInclusion receives two strings of lowercase English letters, s1 and s2. It returns true when some substring of s2 is a permutation of s1: a run of consecutive letters of s2 that holds the same letters as s1, each one as many times, in any order. For "abb", the permutations are "abb", "bab" and "bba".

With s1 = "ab" and s2 = "eidbaooo" the answer is true, because s2 contains "ba" at indexes 3 and 4. With s2 = "eidboaoo" it is false: s2 has an a and a b, but never next to each other. With s1 = "adc" and s2 = "dcda" it is true: the last three letters, "cda", hold one a, one c and one d, just like "adc", while the first three, "dcd", have two d's and no a.

So the question is whether s2 has a window, exactly as long as s1, that holds every letter of s1 the right number of times. The statement asks for O(n + m) time, where n is the length of s2 and m the length of s1, and O(1) extra space: one count for each of the 26 letters.

Approach: a window that keeps count as it slides

The direct way counts the letters of every substring of s2 of length m from scratch and compares with the counts of s1. That costs O(n · m), which is too slow when both strings are 100,000 letters long.

The faster way slides a window one letter at a time and updates the counts instead of recounting. Moving the window right adds one letter at its right end and, once the window is full, removes one at its left end. Each letter of s2 enters once and leaves once, so the work is O(n).

To avoid comparing two 26-entry arrays at every step, the solution keeps one array and one number:

need[x] says how many more copies of letter x the window still needs. It starts as the count of the letter in s1. A letter that the window holds too many of makes it negative.
missing says how many letters of s1 the window still lacks in total. It starts as the length of s1.

When a letter enters and need for it is above 0, the window gains something it lacked, so missing drops by 1. When missing reaches 0, the window holds every letter of s1 as many times as s1 has it. The window is exactly as long as s1, so it has no room for any other letter: it is a permutation.

The trace for "ab" in "eidbaooo" shows the idea. The values are missing after each letter has been processed:

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 letters e, i and d are not in s1, so missing stays at 2. The b brings it to 1, the a to 0, and the method returns true with the window covering "ba".

Step by step

Copy the letters of s2 into an array. A Swift String can't be indexed with an integer, so chars is Array(s2.utf8). For lowercase letters each byte is one letter, and chars[i] is its code.
Create need as an array of 26 zeros, one slot per letter: slot 0 for a, slot 1 for b, and so on.
Count the letters of s1 with a loop over s1.utf8.
Add 1 to need[Int(c) - 97]. The code of a is 97 and the lowercase letters have consecutive codes, so this gives 0 for a and 25 for z. Int(...) turns the byte into an Int first. A letter that appears twice in s1 is needed twice.
Set missing to s1.utf8.count, the number of letters the empty window lacks.
Loop over the right end of the window, last, from 0 to the end of chars. Each pass adds the letter at index last.
Find the new letter's number in code.
Count it as found if it was needed. If need[code] is above 0, subtract 1 from missing. When the count is 0 or less, the window already has all the copies s1 asks for, and this one is extra.
Subtract 1 from need[code], because the window holds one more of this letter.
Check whether the window is now too long. When last >= s1.utf8.count, the window has one letter more than s1, and its first letter has to leave.
Find the leaving letter, chars[last - s1.utf8.count], in oldCode.
Add 1 to need[oldCode], which undoes what that letter did when it came in.
Update missing. If need[oldCode] is now above 0, the window lost a letter that s1 needs, so add 1 to missing. If the count is still 0 or less, the window had a spare copy and lost nothing.
Test for a match. If missing is 0, return true.
Return false after the loop. No window matched. This is also the answer when s1 is longer than s2, since missing can never reach 0 then.

The solution in Swift

class Solution {
    func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        let chars = Array(s2.utf8)
        var need = [Int](repeating: 0, count: 26)
        for c in s1.utf8 {
            need[Int(c) - 97] += 1
        }
        var missing = s1.utf8.count
        for last in 0..<chars.count {
            let code = Int(chars[last]) - 97
            if need[code] > 0 { missing -= 1 }
            need[code] -= 1
            if last >= s1.utf8.count {
                let oldCode = Int(chars[last - s1.utf8.count]) - 97
                need[oldCode] += 1
                if need[oldCode] > 0 { missing += 1 }
            }
            if missing == 0 { return true }
        }
        return false
    }
}

The Swift details worth knowing:

Why not index the string? Swift strings are collections of Character values, and a character can span several bytes, so there is no s[i]. Either you walk a String.Index or you copy the content into an array. Here, Array(s2.utf8) gives an array of UInt8 codes: for "abc" it is [97, 98, 99].
s1.utf8.count counts bytes, which for lowercase ASCII letters equals the number of letters.
Int(c) before the subtraction. The bytes are UInt8, and Swift does not mix integer types. Converting to Int first also keeps the subtraction from trapping: in Swift, arithmetic overflow, including going below zero on an unsigned type, crashes the program at run time.
Negative counts are normal. need is an array of Int, so a letter that the window holds too many of simply goes below 0.
The ranges. 0..<chars.count excludes the upper bound, so the last pass uses the last index.

Complexity

Time: O(n + m). Counting the letters of s1 takes O(m). The window loop runs once per letter of s2 and does a constant number of operations on each pass, which is O(n). Copying s2 into chars is also O(n).

Space: O(1) for the counts, a fixed 26 entries. The chars copy of s2 is an array of n bytes, a convenience that Swift's string design makes necessary.

Edge cases and common mistakes

s1 longer than s2. "abc" in "ab" gives false: the window can't hold three letters out of two.
Equal strings. "abc" in "abc" gives true, since a string is a permutation of itself. A single letter works too: "a" in "a" gives true.
Repeated letters. "aab" in "baa" gives true, but "aab" in "abbab" gives false: no window of three holds two a's and a b. Counting only which letters occur, not how many times, would wrongly accept the second.
Letters that are all there but not contiguous. "ab" in "eidboaoo" gives false. The window must be a run of consecutive letters.
Removing the old letter too early. The check last >= s1.utf8.count keeps the window at exactly the length of s1. If it were >, the window would hold one letter too many when tested.
Forgetting to update missing when a letter leaves. The count in need then drifts from missing, and later windows give wrong answers.

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 = "aab", s2 = "abbab" gives false.
s1 = "hello", s2 = "ooolleoooleh" gives false.

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

Start learning free