Permutation in String

Q: What is the time complexity of Permutation in String?

With a sliding window it is O(m + n) , where m is the length of s1 and n the length of s2 . You count s1 once, then each letter of s2 enters the window once and leaves it once. Recounting every window from scratch costs O(n · m) instead.

Q: Is Permutation in String the same as finding an anagram inside a string?

Yes. A permutation of s1 is an anagram of it, so the question is whether some substring of s2 of length m is an anagram of s1 . The anagram check between two whole strings compares letter counts once; here the same comparison runs on a window that slides along s2 .

Q: Why is the sliding window a fixed size here?

Every permutation of s1 has exactly m letters, so only windows of length m can match. Problems such as the longest substring without repeats grow and shrink the window; here both edges move together, one step at a time.

MediumSliding window Hashing

+10

A permutation of a string uses the same letters in any order, each one as many times as the original does: tar, rat and art are permutations of each other. You get two strings s1 and s2 made of lowercase English letters. Return true if some permutation of s1 appears in s2 as a substring (a run of consecutive characters), and false otherwise.

Function

checkInclusion(s1: string, s2: string) → boolean

s1string: the letters to rearrange
s2string: the string to search in
Returnsboolean: true if a substring of s2 is a rearrangement of s1

Constraints

1 ≤ s1.length ≤ 2 × 10⁴
1 ≤ s2.length ≤ 5 × 10⁴
s1 and s2 contain only lowercase English letters (a to z).
s1 may be longer than s2.

Examples

Input: s1 = "tar"s2 = "smartphone"
Output: true
Explanation: The substring art at indices 2 to 4 of smartphone holds one a, one r and one t, the same letters as tar.

Input: s1 = "noon"s2 = "onion"
Output: false
Explanation: The substrings of length 4 are onio and nion. noon needs two ns and two os, and each window has an i instead of one of them. Every letter of noon appears in onion, but no window has the right counts.

Input: s1 = "abcd"s2 = "dcb"
Output: false
Explanation: Any permutation of abcd has 4 letters, and dcb has only 3, so it cannot contain one.

+17 hidden tests on Submit

Follow-up

Can you return every index of s2 where a permutation of s1 starts, still in O(m + n) time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Listing the permutations of s1 is hopeless: 10 letters already have 3,628,800 orderings. The way out is to stop caring about order. A substring of s2 is a permutation of s1 exactly when it has the same length m and the same count of every letter. So every candidate is a window of the same fixed length, and you can slide one window across s2, updating its letter counts by one letter in and one letter out per step.

Count every window from scratch

Correct, but does not finish on the largest tests

Intuition

The literal reading, build every permutation of s1 and search for it, dies at once: 20 letters have more than 2 × 10^18 orderings. Turn the question around instead. A substring of s2 is a permutation of s1 when it has exactly m letters and uses each letter as many times as s1 does. The order inside it never matters.

So count the letters of s1 once in a table of 26 numbers, index 0 for a and 25 for z. Then take every substring of s2 of length m, count its letters in a fresh table, and compare the two tables. For tar in smartphone, the windows are sma, mar, art and so on, and art matches: one a, one r, one t.

This is correct because it looks at every candidate. It is slow because neighbouring windows share m-1 letters and you recount all of them. With m = 15,000 and n = 50,000 there are 35,001 windows of 15,000 letters each, about 5 × 10^8 steps.

Algorithm

If s1 is longer than s2, return false.
Count the letters of s1 in a table need of 26 zeros.
For every start index from 0 to n-m, count the letters of the m characters from that start in a fresh table.
If that table equals need, return true.
After the last window, return false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26  # need[0] is 'a', need[25] is 'z'
    for ch in s1:
        need[ord(ch) - 97] += 1
    for start in range(n - m + 1):
        # Count the letters of s2[start : start + m] from scratch
        window = [0] * 26
        for i in range(start, start + m):
            window[ord(s2[i]) - 97] += 1
        if window == need:
            return True
    return False

Slide the window and compare 26 counts

Intuition

Two neighbouring windows differ in two letters only. Moving from mar to art drops the m on the left and adds the t on the right. So keep one table for the current window and change it with one +1 and one -1 per step, instead of counting m letters again.

Fill need from s1 and window from the first m letters of s2, and compare them. Then for every i from m to n-1, add s2[i], remove s2[i-m], and compare again. The window is now s2[i-m+1..i], still m letters long.

Each step costs two updates and a comparison of 26 numbers, whatever m is. On the largest input that is about 26 × 50,000 = 1.3 × 10^6 operations, linear in the length of s2. This is the solution most interviewers expect.

Algorithm

If s1 is longer than s2, return false.
Count s1 into need and the first m letters of s2 into window.
If the two tables are equal, return true.
For each i from m to n-1: add 1 for s2[i], subtract 1 for s2[i-m], and return true if the tables are equal.
Return false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26
    window = [0] * 26
    for i in range(m):
        need[ord(s1[i]) - 97] += 1
        window[ord(s2[i]) - 97] += 1  # the first window is s2[0 : m]
    if window == need:
        return True
    for i in range(m, n):
        window[ord(s2[i]) - 97] += 1      # s2[i] enters on the right
        window[ord(s2[i - m]) - 97] -= 1  # s2[i - m] leaves on the left
        if window == need:
            return True
    return False

Slide the window and track unbalanced letters

Intuition

Comparing 26 numbers at every step repeats work, because a step changes only two of them. Keep one table balance instead: balance[c] is how many copies of letter c s1 has minus how many the window has. The window is a permutation of s1 exactly when all 26 balances are 0. Next to the table, keep unbalanced, the number of letters whose balance is not 0, and answer true the moment it reaches 0.

The bookkeeping has one rule. Before you change balance[c], if it is 0, the letter is about to leave balance, so add 1 to unbalanced. After the change, if it is 0, the letter has reached balance, so subtract 1. A letter entering the window lowers its balance by 1; a letter leaving it raises its balance by 1. A balance moving from 2 to 1 triggers neither check, which is right: the letter was unbalanced and still is.

Walk through tar and smartphone. The balances start at a: 1, r: 1, t: 1, so unbalanced is 3. s and m enter and push it to 5, then a enters and brings a to 0: 4. r enters (3) while s leaves (2). t enters (1) while m leaves (0), and the window art is the answer.

You can test unbalanced == 0 from the very first letter. While the window holds fewer than m letters, the balances add up to a positive number, so at least one is not 0. Every step does a fixed amount of work, so the whole scan is O(m + n), and the table always holds 26 numbers, which is O(1) space.

Algorithm

If s1 is longer than s2, return false.
Count s1 into balance and set unbalanced to the number of letters with a balance other than 0.
For each index i of s2, subtract 1 from the balance of s2[i], adding 1 to unbalanced if that balance was 0 and subtracting 1 if it becomes 0.
If i ≥ m, add 1 to the balance of s2[i-m] with the same bookkeeping.
If unbalanced is 0, return true. After the loop, return false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    # balance[c]: copies of letter c in s1 minus copies in the window
    balance = [0] * 26
    for ch in s1:
        balance[ord(ch) - 97] += 1
    unbalanced = sum(1 for b in balance if b != 0)
    for i in range(n):
        # s2[i] enters the window on the right
        c = ord(s2[i]) - 97
        if balance[c] == 0:
            unbalanced += 1
        balance[c] -= 1
        if balance[c] == 0:
            unbalanced -= 1
        # s2[i - m] leaves on the left once the window would pass m letters
        if i >= m:
            c = ord(s2[i - m]) - 97
            if balance[c] == 0:
                unbalanced += 1
            balance[c] += 1
            if balance[c] == 0:
                unbalanced -= 1
        if unbalanced == 0:
            return True
    return False

Pitfalls and edge cases

Most wrong answers come from the edges of the window, or from checking which letters appear instead of how many times.

Checking only that every letter of s1 is in the window. onio holds every letter of noon, yet it is not a permutation of it. Compare counts.
Removing the wrong letter. When s2[i] enters, the letter that leaves is s2[i-m], so the window becomes s2[i-m+1..i]. Removing s2[i-m+1] leaves a window of m-1 letters.
Skipping the first window. If you compare only after sliding, a permutation at index 0 is never found.
Forgetting the case where s1 is longer than s2. In Rust, n - m on unsigned lengths underflows, and in Swift the range 0...(n - m) crashes. Return false first.
Comparing arrays with == in a language where that compares references. In JavaScript and Dart two different arrays are never ==; in Java use Arrays.equals.

Frequently asked questions4

What is the time complexity of Permutation in String?

With a sliding window it is O(m + n), where m is the length of s1 and n the length of s2. You count s1 once, then each letter of s2 enters the window once and leaves it once. Recounting every window from scratch costs O(n · m) instead.

Is Permutation in String the same as finding an anagram inside a string?

Yes. A permutation of s1 is an anagram of it, so the question is whether some substring of s2 of length m is an anagram of s1. The anagram check between two whole strings compares letter counts once; here the same comparison runs on a window that slides along s2.

Why is the sliding window a fixed size here?

Every permutation of s1 has exactly m letters, so only windows of length m can match. Problems such as the longest substring without repeats grow and shrink the window; here both edges move together, one step at a time.

Can I use a hash map instead of an array of 26 counters?

Yes, and you need one if the strings can hold any character. With only lowercase letters, an array of 26 is faster and uses constant space. With a map, delete a key when its count drops to 0 so that two maps with the same letters compare equal, or keep the unbalanced counter from the last approach, which works the same way with a map.

Python

def checkInclusion(s1, s2):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s1 = "tar"
s2 = "smartphone"

Expected

true

Permutation in String

Function

Constraints

Examples

Hints

Solution

Count every window from scratch

Slide the window and compare 26 counts

Slide the window and track unbalanced letters

Pitfalls and edge cases

Frequently asked questions4

Similar problems