Permutation in String

mediumSliding Window118 stepsJava · Python · C++

Does s2 contain a permutation of s1? Slide a window of length |s1| over s2 and compare letter counts. Keep a matches counter of how many of the 26 letters have equal counts, so each slide costs O(1).

▶ Watch the animated trace

Traced input: s1 = "ab", s2 = "eidbaooo" → true. Original problem: neetcode.io/problems/permutation-string

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(1)

n = |s2|. Two arrays of 26 counts.

Key idea

A permutation has the same letter counts, so compare count arrays.
The window has fixed size |s1|: add the new right letter, remove the old left letter.
matches == 26 means the window is a permutation.

Common mistakes

Comparing full 26-entry arrays each slide is O(26n), still fine but slower.
Not handling |s1| > |s2| (answer false).
Updating matches incorrectly when a count moves away from equal.

Solution

Java

boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) return false;
    int[] need = new int[26], win = new int[26];
    for (int i = 0; i < s1.length(); i++) {
        need[s1.charAt(i) - 'a']++;
        win[s2.charAt(i) - 'a']++;
    }
    int matches = 0;
    for (int i = 0; i < 26; i++) if (need[i] == win[i]) matches++;
    int m = s1.length();
    for (int r = m; r < s2.length(); r++) {
        if (matches == 26) {
            return true;
        }
        int in = s2.charAt(r) - 'a', out = s2.charAt(r - m) - 'a';
        win[in]++;
        if (win[in] == need[in]) matches++;
        else if (win[in] == need[in] + 1) matches--;
        win[out]--;
        if (win[out] == need[out]) matches++;
        else if (win[out] == need[out] - 1) matches--;
    }
    return matches == 26;
}

Python

def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2): return False
    need, win = [0] * 26, [0] * 26
    for i in range(len(s1)):
        need[ord(s1[i]) - 97] += 1
        win[ord(s2[i]) - 97] += 1
    matches = sum(need[i] == win[i] for i in range(26))
    m = len(s1)
    for r in range(m, len(s2)):
        if matches == 26:
            return True
        i, o = ord(s2[r]) - 97, ord(s2[r - m]) - 97
        win[i] += 1
        if win[i] == need[i]: matches += 1
        elif win[i] == need[i] + 1: matches -= 1
        win[o] -= 1
        if win[o] == need[o]: matches += 1
        elif win[o] == need[o] - 1: matches -= 1
    return matches == 26

C++

bool checkInclusion(string s1, string s2) {
    if (s1.size() > s2.size()) return false;
    int need[26] = {0}, win[26] = {0};
    for (size_t i = 0; i < s1.size(); i++) {
        need[s1[i] - 'a']++;
        win[s2[i] - 'a']++;
    }
    int matches = 0;
    for (int i = 0; i < 26; i++) if (need[i] == win[i]) matches++;
    int m = s1.size();
    for (int r = m; r < (int)s2.size(); r++) {
        if (matches == 26) {
            return true;
        }
        int in = s2[r] - 'a', out = s2[r - m] - 'a';
        win[in]++;
        if (win[in] == need[in]) matches++;
        else if (win[in] == need[in] + 1) matches--;
        win[out]--;
        if (win[out] == need[out]) matches++;
        else if (win[out] == need[out] - 1) matches--;
    }
    return matches == 26;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
No permutation 'b' and 'a' are never adjacent.	`s1 = "ab", s2 = "eidboaoo"`	`false`
s1 longer than s2 Rejected immediately.	`s1 = "abc", s2 = "ab"`	`false`
Equal strings The first window already matches.	`s1 = "abc", s2 = "cba"`	`true`
Repeated letters "baa" at the start has two a's and one b.	`s1 = "aab", s2 = "baaab"`	`true`