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) .

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 whole-string anagram check compares counts once; here it runs on a sliding window.

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 windows of length 4 are onio and nion. noon needs two ns and two os, and each window has an i in place of one of them.

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.

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 permutations is hopeless: 10 letters already have 3,628,800 orderings. Ignore order instead. A substring of s2 is a permutation of s1 exactly when it has length m and the same count of every letter. So slide one window of length m across s2, updating its 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

Count the letters of s1 once in a table of 26 numbers. Then take every substring of s2 of length m, count it in a fresh table, and compare. In smartphone the windows are sma, mar, art and so on, and art matches tar.

It checks every candidate, so it is correct. But neighbouring windows share m-1 letters and you recount them all: with m = 2 × 10^4 and n = 5 × 10^4 that is 30,001 windows of 20,000 letters, about 6 × 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

Neighbouring windows differ in two letters: moving from mar to art drops the m and adds the t. So keep one table for the current window and change it with one +1 and one -1 per step.

Each step costs two updates and a comparison of 26 numbers, whatever m is: about 26 × 50,000 = 1.3 × 10^6 operations on the largest input.

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

A step changes only two counts, so comparing all 26 repeats work. Keep balance[c], the copies of c in s1 minus the copies in the window, and unbalanced, the number of letters whose balance is not 0. The window is a permutation of s1 exactly when unbalanced is 0.

One rule keeps the counter right: before you change a balance, add 1 to unbalanced if it was 0; after, subtract 1 if it is 0. A move from 2 to 1 triggers neither, which is right. For tar in smartphone, unbalanced starts at 3. s and m push it to 5, a brings it to 4, r in and s out make 2, and t in and m out make 0 at art.

You can test from the first letter: while the window is shorter than m, the balances add up to a positive number, so one of them is not 0.

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

Checking only that every letter of s1 is in the window. onio holds every letter of noon but is not a permutation of it.
Removing the wrong letter. When s2[i] enters, s2[i-m] leaves; removing s2[i-m+1] drops a letter that is still inside the window.
Skipping the first window. If you compare only after sliding, tar at index 0 of tarp is never found.
Not returning false first when s1 is longer than s2. In Rust n - m on unsigned lengths underflows, and in Swift the range 0...(n - m) crashes.
Comparing arrays with == where that compares references, as in JavaScript and Dart. In Java use Arrays.equals.

Frequently asked questions3

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).

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 whole-string anagram check compares counts once; here it runs on a sliding window.

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 lowercase letters only, an array of 26 is faster. With a map, delete a key when its count drops to 0 so that maps with the same letters compare equal, or use the unbalanced counter, which works the same with a map.

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

Test #1

Test #2

Test #3

Arguments

s1 = "tar"
s2 = "smartphone"

Expected Output

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 questions3

Similar problems