Start learning free

LESSON 393 OF 569 · SLIDING WINDOW

Permutation in String in Python: O(n + m) Sliding Window with Counts

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

PYTHON · SLIDING WINDOW

Permutation In String in Python, explained

Problem overview

The method 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 the same number of times in any order, so "abb", "bab" and "bba" are all permutations of each other. A substring is a run of consecutive characters.

With s1 = "ab" and s2 = "eidbaooo" the answer is True: the letters at indexes 3 and 4 are "ba". With s2 = "eidboaoo" the answer is False. That string has an a and a b, but never next to each other. With s1 = "adc" and s2 = "dcda" the answer 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: one count for each of the 26 letters.

Approach: a window as long as s1, with a count of what it still lacks

A matching substring has exactly len(s1) letters, so only windows of that length matter. The slow approach counts the letters of each window from scratch, which costs O(n · m). The faster approach slides one window across s2 and updates the counts as it moves: one letter comes in on the right and, once the window is full, one leaves on the left. Each letter of s2 enters once and leaves once.

The list need has one slot per letter and describes what the window still needs. At the start it holds the letters of s1. When a letter enters the window its slot goes down by 1, and when a letter leaves it goes up by 1. A slot above 0 means the window lacks copies of that letter. A slot at 0 or below means the window has all it needs, and a negative slot means it holds extras.

Checking all 26 slots after every move would cost 26 steps each time. A single counter, missing, avoids that: it counts the letters of s1 the window still lacks. It starts at len(s1) and changes only when a needed copy comes in (it goes down) or a needed copy leaves (it goes up). When missing reaches 0, the window holds every letter of s1 as many times as s1 has it. A window of exactly that length has no room for anything else, so it is a permutation.

Here is the first example, s1 = "ab" and s2 = "eidbaooo". The last column lists the nonzero slots of need after each turn:

`last`	new letter	`missing`	nonzero slots of `need`
0	e	2	a: 1, b: 1, e: -1
1	i	2	a: 1, b: 1, e: -1, i: -1
2	d	2	a: 1, b: 1, d: -1, i: -1
3	b	1	a: 1, d: -1
4	a	0	(none)

At last = 2 the e leaves, because the window is longer than s1. At last = 4 the window is "ba", nothing is missing, and the method returns True.

Step by step

Create need as [0] * 26: slot 0 for a, slot 1 for b, and so on.
Loop over s1 with c as the letter.
Count each letter by adding 1 to need[ord(c) - ord('a')]. ord gives a character's code, and the codes of a to z are consecutive, so subtracting the code of 'a' gives 0 to 25.
Set missing to len(s1): the empty window lacks every letter.
Slide the window with a loop where last goes over range(len(s2)). Each turn adds the letter at last on the right.
Compute the new letter's slot and store it in code.
If need[code] is above 0, this letter was still needed: subtract 1 from missing.
Subtract 1 from need[code], whether or not it was needed. It can go negative.
Check whether the window is too long with last >= len(s1). If so, the first letter, s2[last - len(s1)], has to leave.
Compute the leaving letter's slot and store it in oldCode.
Add 1 to need[oldCode]: the window no longer holds it.
If need[oldCode] is now above 0, the window lost a letter that s1 needs: add 1 to missing.
If missing is 0, return True.
After the loop, return False. No window matched. When s1 is longer than s2, missing never reaches 0, so this is the answer too.

The solution in Python

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        need = [0] * 26
        for c in s1:
            need[ord(c) - ord('a')] += 1
        missing = len(s1)
        for last in range(len(s2)):
            code = ord(s2[last]) - ord('a')
            if need[code] > 0:
                missing -= 1
            need[code] -= 1
            if last >= len(s1):
                oldCode = ord(s2[last - len(s1)]) - ord('a')
                need[oldCode] += 1
                if need[oldCode] > 0:
                    missing += 1
            if missing == 0:
                return True
        return False

Python details worth knowing:

Why test before subtracting. The check need[code] > 0 must run before need[code] -= 1. A letter that arrives when its slot is 0 or negative is a spare copy and must not lower missing.
Likewise on the way out. The slot goes up first, then the test need[oldCode] > 0 runs. Only a slot that ends above 0 means the window gave up a copy that s1 needs.
Characters are strings. Iterating over a string gives one-character strings. ord turns one into its integer code, and ord('a') is the base for the subtraction.
Negative slots are fine. A list slot has no lower bound. A count of -1 simply records an extra copy in the window.

Complexity

Time: O(n + m). Counting s1 takes m steps. The main loop runs n times and does a constant amount of work in each turn: a few list reads and writes and no inner loop.

Space: O(1). The list need always has 26 slots, whatever the lengths of the strings.

Edge cases and common mistakes

s1 longer than s2. "abc" and "ab" return False. The window never reaches the length of s1, so missing stays above 0.
Repeated letters. "abb" in "ab" returns False, and "aab" in "abaa" returns True (the window "baa"). A plain set of letters would treat "ab" like "aab", so counts are needed, not just presence.
Single letters. "a" in "a" returns True and "a" in "b" returns False. When s1 has one letter, the window is full from the first turn.
Window one letter off. The test last >= len(s1) removes a letter only once the window holds len(s1) + 1 letters. Using > would let the window grow to len(s1) + 1 letters, which can report a match that doesn't exist: s1 = "ab" in s2 = "axb" would return True, though the correct answer is False.
Comparing whole count lists. Comparing two 26-slot lists for every window works and is correct, but costs 26 steps per turn. The missing counter keeps each turn constant.

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

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

Start learning free