Start learning free

LESSON 393 OF 569 · SLIDING WINDOW

Permutation in String in Java: O(n + m) Sliding Window, 26 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

JAVA · SLIDING WINDOW

Permutation In String in Java, 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, exactly as long as s1, that holds every letter as many times as s1 does. Otherwise it returns false.

With s1 = "ab" and s2 = "eidbaooo", the substring "ba" at indexes 3 and 4 is a permutation of "ab", so the answer is true. With s2 = "eidboaoo" the letters a and b both occur, but never next to each other, so the answer is false. With s1 = "adc" and s2 = "dcda", the last three letters, "cda", hold one a, one c and one d, so the answer is true, while the first three, "dcd", have two d's and no a.

Approach: a window of s1's length that slides right

Checking every substring of s2 on its own, by sorting it or counting its letters, takes O(n · m) time for n = s2.length() and m = s1.length(). With strings of 100,000 letters that is too slow. The faster idea is to keep a window over s2 and update it as it slides, instead of rebuilding it.

The window needs the same size as s1. Since it can then hold no letter that s1 lacks without also lacking a letter s1 has, the window is a permutation of s1 exactly when it contains every letter of s1 with its full count. To track this, the lesson keeps two things:

need, an int[26]. need[0] counts how many more a's the window still needs, need[1] the b's, and so on. It starts as the letter counts of s1. A letter that the window holds in excess pushes its count below 0.
missing, the number of letters of s1 that the window still lacks. It starts at s1.length(), and when it reaches 0 the window is a match.

Each letter of s2 enters the window once and leaves it once, so the whole scan is O(n), plus O(m) to count s1 at the start.

Here is the scan for s1 = "ab" and s2 = "eidbaooo". It stops as soon as missing is 0:

last=0 window=e missing=2
last=1 window=ei missing=2
last=2 window=id missing=2
last=3 window=db missing=1
last=4 window=ba missing=0
-> true

The letters e, i and d are not in s1, so they change nothing. The b at index 3 brings missing down to 1, and the a at index 4 brings it to 0. For a failing case, s1 = "aab" and s2 = "acbb":

last=0 window=a missing=2
last=1 window=ac missing=2
last=2 window=acb missing=1
last=3 window=cbb missing=2
-> false

At index 3 the second b is extra, since s1 has only one, so it doesn't lower missing. The a that leaves at the same time does raise it back to 2.

Step by step

Create need as an int[26]. Java fills a new int array with zeros.
Count the letters of s1 with a for-each loop over s1.toCharArray().
Add 1 to need[c - 'a']. A char is a number in Java, and a to z have consecutive codes, so c - 'a' is 0 for a, 1 for b, and so on. A letter that appears twice in s1 is needed twice.
Store s1.length() in missing: before the window holds anything, it lacks every letter.
Loop with last over every index of s2. Each turn adds the letter at last on the window's right end.
Store the new letter's number from 0 to 25 in code.
If need[code] is above 0, decrement missing. A count of 0 or less means the window already holds all the copies s1 has, so this one is extra.
Decrement need[code]: the window holds one more of this letter. The count can go below 0.
Check whether the window got longer than s1: last >= s1.length(). Then the first letter, s2.charAt(last - s1.length()), has to leave, so that every window you test is exactly as long as s1.
Store the leaving letter's number in oldCode.
Increment need[oldCode], which undoes what the letter did when it came in.
If need[oldCode] is now above 0, increment missing: the window lost a letter that s1 needs. If the count is still 0 or less, the window had a spare copy.
If missing is 0, return true. 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. This also covers s1 longer than s2, where missing never gets to 0.

The solution in Java

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int[] need = new int[26];
        for (char c : s1.toCharArray()) {
            need[c - 'a']++;
        }
        int missing = s1.length();
        for (int last = 0; last < s2.length(); last++) {
            int code = s2.charAt(last) - 'a';
            if (need[code] > 0) missing--;
            need[code]--;
            if (last >= s1.length()) {
                int oldCode = s2.charAt(last - s1.length()) - 'a';
                need[oldCode]++;
                if (need[oldCode] > 0) missing++;
            }
            if (missing == 0) return true;
        }
        return false;
    }
}

Java details:

char arithmetic. c - 'a' subtracts two char values and gives an int, which is what an array index needs. It only works for lowercase letters, which the constraints guarantee.
toCharArray() versus charAt. The first loop copies the string into an array to use a for-each. The main loop uses charAt(i), because it needs the index anyway.
Why a negative count is fine. need is an ordinary int array. Dropping below 0 records "the window has more of this letter than s1", and the later increments bring it back.
One-line ifs. if (need[code] > 0) missing--; has no braces; that is fine for a single statement, but adding a second line later would not be part of the if.

Complexity

Time: O(n + m). Counting s1 is O(m). The main loop makes at most n turns, and each turn adds one letter, removes at most one, and does a constant amount of work.

Space: O(1). need always has 26 slots, whatever the lengths. (toCharArray() makes a copy of s1; the lesson's bound counts the extra storage of the algorithm itself, the 26 counts.)

Edge cases and common mistakes

s1 longer than s2. "abc" in "ab" gives false: the window can never hold three letters.
Same size. "a" in "a" gives true.
Repeated letters. Comparing only which letters occur is wrong. "ab" in "aab" gives true (the substring "ab"), but "aab" in "abb" gives false, because the string has one a where two are needed.
Not sliding the window. If the first letter never leaves, the window grows past s1.length() and counts letters from far away. "hello" in "ooolleoooleh" gives false, because no window of five letters has the right counts.
Extra letters. A letter that s1 doesn't need must not lower missing. That is why step 7 tests need[code] > 0 first.

Testing

s1 = "ab", s2 = "eidbaooo" gives true.
s1 = "ab", s2 = "eidboaoo" gives false.
s1 = "adc", s2 = "dcda" gives true.
s1 = "aab", s2 = "abab" gives true.
s1 = "abb", s2 = "abcabbc" gives true.
s1 = "abc", s2 = "ab" gives false.

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

Start learning free