Permutation in String

Problem

Given strings s1 and s2, return true iff s2 contains any permutation of s1 as a contiguous substring.

Constraints

• 1 ≤ s1.length ≤ s2.length ≤ 10⁴

Approach — Sliding Window

This is a Sliding Window problem. The idea: keep a moving window over the sequence, expanding and shrinking it while tracking the answer in a single pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def checkInclusion(self, s1, s2):
        from collections import Counter
        need = Counter(s1)
        k = len(s1)
        window = Counter(s2[:k])
        if window == need:
            return True
        for i in range(k, len(s2)):
            window[s2[i]] += 1
            window[s2[i - k]] -= 1
            if window[s2[i - k]] == 0:
                del window[s2[i - k]]
            if window == need:
                return True
        return False

Java

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;
        int[] a = new int[26], b = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            a[s1.charAt(i) - 'a']++;
            b[s2.charAt(i) - 'a']++;
        }
        for (int i = s1.length(); i < s2.length(); i++) {
            if (matches(a, b)) return true;
            b[s2.charAt(i) - 'a']++;
            b[s2.charAt(i - s1.length()) - 'a']--;
        }
        return matches(a, b);
    }
    private boolean matches(int[] a, int[] b) {
        for (int i = 0; i < 26; i++) if (a[i] != b[i]) return false;
        return true;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.