Problem statement

Given two strings s1 and s2, return true if s2 contains a permutation of s1 as a substring.

Example 1

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: "ba" is a permutation of "ab".

Example 2

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints

• 1 <= s1.length <= 6
• 1 <= s2.length <= 40
• Lowercase English letters.

Hints for Permutation in String

1. Hint 1

   A permutation match is a frequency-count match over a window of length |s1|.

2. Hint 2

   Slide the window over s2, updating counts incrementally.

How to solve Permutation in String

A permutation of s1 is any arrangement of exactly its letters, so a substring is a permutation precisely when it has the same length and the same letter frequencies. Slide a fixed-width window of length |s1| across s2 and compare frequency tables.

Approach

1. Return false immediately if s1 is longer than s2.
2. Build a 26-slot frequency table for s1, and one for the first window of s2.
3. Compare the tables; a match means a permutation was found.
4. Slide the window one character right: add the entering character and remove the leaving one.
5. Repeat to the end of s2.

Why it works

Two strings of equal length are permutations of one another exactly when their multisets of characters agree, and a 26-slot count is that multiset. Updating incrementally is what keeps this linear — each slide touches only two counters instead of rebuilding the whole table, so the total work is O(|s2| · 26) rather than O(|s2| · |s1|).

Complexity

• Time — O(|s2| · 26)
• Space — O(1)

Pitfalls

• The window is fixed width; growing and shrinking it as in a variable window solves a different problem.
• Guard the length check first, otherwise the first window runs off the end of s2.
• Remove the character leaving the window as well as adding the one entering — forgetting the removal turns counts into cumulative totals.
• Compare full tables (or maintain a running count of matching slots); comparing only the entering character is not enough.

Reference solution

Python

def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2):
        return False
    need = [0] * 26
    have = [0] * 26
    for ch in s1:
        need[ord(ch) - 97] += 1
    for i, ch in enumerate(s2):
        have[ord(ch) - 97] += 1
        if i >= len(s1):
            have[ord(s2[i - len(s1)]) - 97] -= 1
        if i >= len(s1) - 1 and have == need:
            return True
    return False

Java

public static boolean checkInclusion(String s1, String s2) {
    int n1 = s1.length(), n2 = s2.length();
    if (n1 > n2) return false;
    int[] need = new int[26];
    int[] have = new int[26];
    for (int i = 0; i < n1; i++) need[s1.charAt(i) - 'a']++;
    for (int i = 0; i < n2; i++) {
        have[s2.charAt(i) - 'a']++;
        if (i >= n1) have[s2.charAt(i - n1) - 'a']--;
        if (i >= n1 - 1 && Arrays.equals(need, have)) return true;
    }
    return false;
}

C++

bool checkInclusion(string s1, string s2) {
    int n1 = (int) s1.size(), n2 = (int) s2.size();
    if (n1 > n2) return false;
    vector<int> need(26, 0), have(26, 0);
    for (int i = 0; i < n1; i++) need[s1[i] - 'a']++;
    for (int i = 0; i < n2; i++) {
        have[s2[i] - 'a']++;
        if (i >= n1) have[s2[i - n1] - 'a']--;
        if (i >= n1 - 1 && need == have) return true;
    }
    return false;
}

JavaScript

var checkInclusion = function(s1, s2) {
    if (s1.length > s2.length) return false;
    const need = new Array(26).fill(0);
    const have = new Array(26).fill(0);
    for (const ch of s1) need[ch.charCodeAt(0) - 97]++;
    for (let i = 0; i < s2.length; i++) {
        have[s2.charCodeAt(i) - 97]++;
        if (i >= s1.length) have[s2.charCodeAt(i - s1.length) - 97]--;
        if (i >= s1.length - 1) {
            let ok = true;
            for (let j = 0; j < 26; j++) {
                if (need[j] !== have[j]) { ok = false; break; }
            }
            if (ok) return true;
        }
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium