Start learning free

LESSON 392 OF 568 · SLIDING WINDOW

Permutation in String in C++: Sliding Window, O(n + m)

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 <= 105
  • 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
    Ctrl + Enter to check

    C++ · SLIDING WINDOW

    Permutation In String in C++, 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 of s1 uses the same letters, each one as many times as in s1, in any order. A substring is a run of consecutive characters of s2.

    So the real question is: does s2 have a run of letters, exactly as long as s1, that holds every letter as many times as s1 does?

    For s1 = "ab" and s2 = "eidbaooo" the answer is true, because s2 contains "ba" at indexes 3 and 4. For s2 = "eidboaoo" it is false: there is an a and a b, but never next to each other. For s1 = "adc" and s2 = "dcda" it is true: the last three letters, "cda", have the same letters as "adc", while the first three, "dcd", have two d's and no a.

    Approach: a window with a running count

    The direct way builds every substring of s2 of length s1.size() and compares its letter counts with those of s1. With strings up to 100,000 letters that takes O(n · m) time, too slow.

    Notice that two neighbouring windows share almost all their letters. Sliding the window one step to the right adds one letter on its right end and removes one on its left end. Instead of recounting, keep a running tally and update it for those two letters only.

    The tally is an array need of 26 counters, one per letter. Start with need holding the counts of s1: that is what an empty window still needs. When a letter enters the window, its counter goes down by one. When a letter leaves, it goes up by one. A counter at 0 means the window holds exactly as many copies of that letter as s1. A negative counter means the window holds too many.

    Checking all 26 counters at every step would cost 26 operations per step. A single integer, missing, avoids that. It counts how many letters of s1 the window still lacks, starting at s1.size(). A letter only reduces missing when it was really needed, that is, when its counter was above 0. When missing reaches 0, the window holds every letter of s1 with its full multiplicity. The window is as long as s1, so it has no room for anything else: it is a permutation.

    Here is the walk for s1 = "ab" and s2 = "eidbaooo", showing the window after the step is done:

    lastletterwindowmissing
    0ee2
    1iei2
    2did2
    3bdb1
    4aba0

    At last = 4, missing is 0 and the method returns true.

    For s1 = "adc" and s2 = "dcda", the second d at last = 2 drives the counter for d to -1 without lowering missing, which stays at 1. At last = 3 the window drops its first d, the counter for d returns to 0 and, since it is not above 0, missing does not grow. The new a lowers missing to 0, so the answer is true.

    Step by step

    1. Create need, a vector<int> of size 26 filled with 0. Index 0 is for a, index 1 for b, and so on.
    2. Loop over s1 with a range-based for and a char c.
    3. Count the letter: need[c - 'a']++. A char is a small number, and the codes of a to z are consecutive, so c - 'a' is 0 for a, 1 for b and so on. A letter that appears twice in s1 is needed twice.
    4. Set missing to s1.size(): the window is empty, so it lacks everything.
    5. Slide over s2. The loop variable last is the index of the letter that enters the window on its right end.
    6. Convert the entering letter to a number from 0 to 25 and store it in code.
    7. If need[code] is above 0, s1 still needed this letter, so decrease missing. At 0 or below, this copy is extra and missing stays.
    8. Decrease need[code], because the window now holds one more of this letter. The counter may become negative.
    9. Check whether the window got too long: last >= s1.size() means it now has s1.size() + 1 letters, so the first one has to leave.
    10. Find the leaving letter, s2[last - s1.size()] - 'a', in oldCode. It is the letter s1.size() places to the left of the new one.
    11. Increase need[oldCode], undoing what that letter did when it came in.
    12. If need[oldCode] is now above 0, the window lost a letter that s1 needs, so increase missing. If the counter is 0 or below, the window had a spare copy and lost nothing.
    13. If missing is 0, return true right away, inside the loop.
    14. Return false after the loop. No window matched. If s1 is longer than s2, missing never reaches 0, so this is also the answer there.

    The solution in C++

    class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int> need(26, 0);
        for (char c : s1) {
            need[c - 'a']++;
        }
        int missing = s1.size();
        for (int last = 0; last < s2.size(); last++) {
            int code = s2[last] - 'a';
            if (need[code] > 0) missing--;
            need[code]--;
            if (last >= s1.size()) {
                int oldCode = s2[last - s1.size()] - 'a';
                need[oldCode]++;
                if (need[oldCode] > 0) missing++;
            }
            if (missing == 0) return true;
        }
        return false;
    }
};

    C++ details worth knowing:

    • Arithmetic on char. s2[last] - 'a' is an int. It is a valid index only because the input holds lowercase letters. A capital letter or a digit would give an index outside 0 to 25 and the code would read or write outside the vector.
    • Signed and unsigned. s1.size() is unsigned, and last is an int. In last >= s1.size() and in last - s1.size(), last is converted to unsigned. That is safe here: last is never negative, and the subtraction only runs when last >= s1.size(), so it can't wrap. Without that guard, last - s1.size() with last = 1 and a three-letter s1 would wrap to a huge number.
    • Strings by value. The method takes string s1, string s2 by value, which copies both strings once. That is fine for the sizes here and does not change the complexity.
    • Keeping the early return. The check missing == 0 sits inside the loop after the update, so the window is tested at every position.

    Complexity

    Time: O(n + m). Counting s1 takes m steps. Each letter of s2 enters the window once and leaves it at most once, and each of those updates costs constant time, giving n turns of constant work.

    Space: O(1). The need vector always has 26 elements, however long the strings are.

    Edge cases and common mistakes

    • s1 longer than s2. "abc" in "ab" returns false: the window never gets enough letters, so missing never reaches 0.
    • Repeated letters. "aa" in "aba" returns false, because the two a's are not adjacent, while "abb" in "xbabx" returns true through the window "bab". Checking only which letters are present would not be enough: the counts matter.
    • Counting the entering letter twice, or forgetting the leaving one. The window would grow beyond s1.size() and would accept strings with extra letters.
    • Testing missing before the window is full. In the first turns the window is shorter than s1, so missing cannot be 0 yet. The method needs no special case for that.
    • Single letters. "a" in "a" gives true and "a" in "b" gives false.

    Testing

    • s1 = "ab", s2 = "eidbaooo" gives true.
    • s1 = "ab", s2 = "eidboaoo" gives false.
    • s1 = "adc", s2 = "dcda" gives true.
    • s1 = "abb", s2 = "xbabx" gives true.
    • s1 = "aa", s2 = "aba" gives false.
    • s1 = "abc", s2 = "ab" gives false.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free