Start learning free

LESSON 400 OF 576 · SLIDING WINDOW

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

Guided

Ctrl + Enter to check

RUST · SLIDING WINDOW

Permutation In String in Rust, explained

Problem overview

The function check_inclusion 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 many times as s1 does, in any order, and a substring is a run of consecutive letters of s2.

So the question is whether s2 has a run of letters, exactly as long as s1, with the same letter counts. For s1 = "ab" and s2 = "eidbaooo" the run "ba" at indexes 3 and 4 qualifies, so the answer is true. For s2 = "eidboaoo" the letters a and b are never next to each other, so the answer is false. For s1 = "adc" and s2 = "dcda" the last three letters, "cda", have one a, one c and one d, so the answer is true, while the first three, "dcd", have two d's and no a.

The lesson asks for O(n + m) time, where n is the length of s2 and m the length of s1, with constant extra space: one count for each of the 26 letters. Counting the letters of every substring from scratch costs O(n · m), which is too slow when both strings have 100,000 letters.

Approach: slide a window and update counts

Every window to test has the same length as s1. Moving the window one place right changes only two letters: one enters on the right and one leaves on the left. So instead of recounting, keep running counts and adjust them by one letter at each end.

The array need holds, for each letter, how many more copies the window still needs to match s1. At the start it holds the counts of s1. When a letter enters the window, its count goes down by one; when it leaves, the count goes up by one. A count below zero means the window has more of that letter than s1 does.

Checking whether all 26 counts are zero after each move would cost 26 steps per window. Instead the code keeps one number, missing, the number of letters of s1 that the window still lacks. It starts at s1.len() and drops to 0 exactly when the window holds every letter of s1 the right number of times. Since the window has the same length as s1, it then has no room for any other letter, so it is a permutation.

The rules for missing are:

A letter enters. If its count in need is above 0, s1 still wanted it, so missing goes down by one. If the count is 0 or less, the copy is extra and missing stays.
A letter leaves. After its count goes up, if it is above 0, the window lost a letter s1 needs, so missing goes up by one. Otherwise the window had a spare copy and nothing needed was lost.

Here is the loop on s1 = "adc" and s2 = "dcda", showing missing after each step:

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 index 2 a second d enters, but s1 has only one d, so missing stays at 1, and the first d leaves when index 3 is processed. At last = 3 the window is "cda" and missing reaches 0. For "ab" in "eidbaooo" the same loop prints missing=2 three times, then 1 at index 3 (the b) and 0 at index 4 (the a).

Step by step

Get the bytes of s2 with s2.as_bytes(). A string can't be indexed by number in Rust, but the byte slice can, and each lowercase letter is one byte.
Create need as [0i32; 26], one count per letter. The counts are signed because they can go below zero.
Loop over s1.bytes() to fill it in.
Add 1 for each letter. c - b'a' is 0 for a, 1 for b, and so on, because the letters have consecutive codes. as usize turns that into an index.
Set missing to s1.len(), the number of letters the window lacks before it holds anything.
Loop over last in 0..bytes.len(). Each turn adds the letter at index last to the right end of the window.
Compute code, the new letter's number from 0 to 25.
Count it if it was needed. If need[code] > 0, subtract 1 from missing.
Update the count: subtract 1 from need[code].
Check whether the window grew too long. When last >= s1.len(), the window has one letter more than s1, so the first letter, at last - s1.len(), must leave.
Find the leaving letter's number in old_code.
Undo its count: add 1 to need[old_code].
Record the loss. If need[old_code] is now above 0, add 1 to missing.
Test for a match. If missing == 0, return true at once. In the first turns the window is shorter than s1, so it can't hold all of its letters yet.
Return false after the loop. When s1 is longer than s2, missing never reaches 0, so this is also the right answer there.

The solution in Rust

impl Solution {
    fn check_inclusion(s1: String, s2: String) -> bool {
        let bytes = s2.as_bytes();
        let mut need = [0i32; 26];
        for c in s1.bytes() {
            need[(c - b'a') as usize] += 1;
        }
        let mut missing = s1.len();
        for last in 0..bytes.len() {
            let code = (bytes[last] - b'a') as usize;
            if need[code] > 0 {
                missing -= 1;
            }
            need[code] -= 1;
            if last >= s1.len() {
                let old_code = (bytes[last - s1.len()] - b'a') as usize;
                need[old_code] += 1;
                if need[old_code] > 0 {
                    missing += 1;
                }
            }
            if missing == 0 {
                return true;
            }
        }
        false
    }
}

The Rust details worth a closer look:

Bytes, not characters. as_bytes() gives a &[u8] borrowed from s2, with no copy. Indexing by byte is correct here because the strings hold only the ASCII letters a to z. For text with other characters, one letter could take several bytes.
Byte literals. b'a' is a u8, the code of the letter a (97). Subtracting two u8 values gives a u8, and since every letter is at least b'a', the result never goes below zero. For b'c' - b'a' the result is 2.
Array syntax. [0i32; 26] is a fixed-size array of 26 zeros on the stack. The i32 suffix on the zero fixes the element type.
Two integer types. need holds i32 counts that may go negative. missing is a usize, like s1.len(), and it is only decreased while some letter is still needed, so it stays between 0 and s1.len().
Return as the last expression. false has no semicolon, so it is the function's value; the return true inside the loop exits early.

Complexity

Time: O(n + m). Counting the letters of s1 takes m steps. The main loop runs n times and each turn does a constant number of operations, because every letter of s2 enters the window once and leaves it once.

Space: O(1). The array has 26 entries, whatever the lengths of the strings.

Edge cases and common mistakes

s1 longer than s2. "abc" in "ab" returns false: the window never gets the three letters it needs.
Repeated letters. s1 = "aab" in "abaa" returns true, because "baa" holds two a's and one b. A set of letters would not tell the difference between one a and two.
A match at the very start or end. The check runs after each turn, so a match in the first s1.len() letters or in the last ones is found. "ab" in "aab" returns true, with the match at the end.
A single letter. "a" in "a" returns true. The window has one letter and nothing ever leaves it.
Counting extras as progress. If the code subtracted from missing on every entering letter, check_inclusion("adc", "dcd") would return true after three letters, although "dcd" has two d's and no a. The test need[code] > 0 keeps spare copies from counting.
Removing the leaving letter too early. The window must reach s1.len() letters before anything leaves, which is what last >= s1.len() checks, after the new letter has gone in.
Large inputs. With 100,000 letters in s2, the loop still makes one pass. A string of 100,000 a's does not contain a permutation of 50,000 b's followed by 50,000 a's, and the function returns false. Reversing that long s1 and using it as s2 returns true.

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 = "a", s2 = "a" gives true.
s1 = "aab", s2 = "abaa" gives true.
s1 = "abb", s2 = "babb" gives true.
s1 = "ab", s2 = "aab" gives true.

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

Start learning free