567. Permutation In String - Explanation

Description

You are given two strings s1 and s2.

Return true if s2 contains a permutation of s1, or false otherwise. That means if a permutation of s1 exists as a substring of s2, then return true.

Both strings only contain lowercase letters.

Example 1:

Input: s1 = "abc", s2 = "lecabee"

Output: true

Explanation: The substring "cab" is a permutation of "abc" and is present in "lecabee".

Example 2:

Input: s1 = "abc", s2 = "lecaabee"

Output: false

Constraints:

1 <= s1.length, s2.length <= 1000

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the maximum of the lengths of the two strings.

Hint 1

A brute force solution would be to check every substring of s2 with s1 by sorting s1 as well as the substring of s2. This would be an O(n^2) solution. Can you think of a better way? Maybe we can use the freqency of the characters of both the strings as we did in checking anagrams.

Hint 2

We return false if the length of s1 is greater than the length of s2. To count the frequency of each character in a string, we can simply use an array of size O(26), since the character set consists of a through z (26 continuous characters). Which algorithm can we use now?

Hint 3

We use a sliding window approach on s2 with a fixed window size equal to the length of s1. To track the current window, we maintain a running frequency count of characters in s2. This frequency count represents the characters in the current window. At each step, if the frequency count matches that of s1, we return true.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

The brute-force approach tries every possible substring of s2 and checks whether it is a permutation of s1.
To do this, we sort s1 once, and then for each substring of s2, we sort it and compare.
If the sorted substring matches the sorted s1, it means the substring contains exactly the same characters.
This method is simple to understand but very slow because it examines all substrings and sorts each one.

Algorithm

Sort s1 so we can compare substrings against it.
Loop through every starting index i in s2.
For each i, loop through every ending index j ≥ i:
- Extract the substring s2[i : j + 1].
- Sort it and compare with sorted s1.
- If they match, return True.
If no matching substring is found, return False.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        s1 = sorted(s1)

        for i in range(len(s2)):
            for j in range(i, len(s2)):
                subStr = s2[i : j + 1]
                subStr = sorted(subStr)
                if subStr == s1:
                    return True
        return False

Time & Space Complexity

Time complexity: $O(n ^ 3 \log n)$
Space complexity: $O(n)$

2. Hash Table

Intuition

We first count the characters in s1, since any valid substring in s2 must match these exact frequencies.
Then, for every starting point in s2, we build a frequency map as we extend the substring.
If we ever exceed the needed count for a character, we stop early because the substring can no longer be a valid permutation.
If all character counts match exactly, we have found a valid permutation.
This method is much cleaner than brute force but still slow because it restarts counting for each position.

Algorithm

Build a frequency map count1 for all characters in s1.
Let need be the number of unique characters in s1 whose counts must match.
For each starting index i in s2:
- Create an empty map count2 and a match counter cur = 0.
- Extend the substring by moving j from i forward:
  - Increment the frequency of s2[j] in count2.
  - If count2[s2[j]] exceeds what count1 requires, break — this substring can’t work.
  - If the count for this character now matches count1, increase cur.
  - If cur == need, return True — we found a valid permutation.
If no starting index yields a match, return False.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        count1 = {}
        for c in s1:
            count1[c] = 1 + count1.get(c, 0)

        need = len(count1)
        for i in range(len(s2)):
            count2, cur = {}, 0
            for j in range(i, len(s2)):
                count2[s2[j]] = 1 + count2.get(s2[j], 0)
                if count1.get(s2[j], 0) < count2[s2[j]]:
                    break
                if count1.get(s2[j], 0) == count2[s2[j]]:
                    cur += 1
                if cur == need:
                    return True
        return False

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(1)$ since we have at most $26$ different characters.

Where $n$ is the length of the string1 and $m$ is the length of string2.

3. Sliding Window

Intuition

Since a permutation of s1 must have the same character counts, we can use a fixed-size sliding window over s2 whose length is exactly len(s1).
We maintain two frequency arrays:

one for s1
one for the current window in s2

If these two arrays ever match, the window is a valid permutation.
As we slide the window forward, we update counts by removing the left character and adding the new right character — no need to rebuild the counts each time.
This makes the solution fast and efficient.

Algorithm

If s1 is longer than s2, return False.
Build character frequency arrays for:
- s1
- the first window of s2 of size len(s1)
Count how many positions match between the two arrays (matches).
Slide the window from left to right across s2:
- At each step, add the new right character and update counts/matches.
- Remove the left character and update counts/matches.
- If at any time matches == 26, return True.
After finishing the loop, return whether matches == 26.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False

        s1Count, s2Count = [0] * 26, [0] * 26
        for i in range(len(s1)):
            s1Count[ord(s1[i]) - ord('a')] += 1
            s2Count[ord(s2[i]) - ord('a')] += 1

        matches = 0
        for i in range(26):
            matches += (1 if s1Count[i] == s2Count[i] else 0)

        l = 0
        for r in range(len(s1), len(s2)):
            if matches == 26:
                return True

            index = ord(s2[r]) - ord('a')
            s2Count[index] += 1
            if s1Count[index] == s2Count[index]:
                matches += 1
            elif s1Count[index] + 1 == s2Count[index]:
                matches -= 1

            index = ord(s2[l]) - ord('a')
            s2Count[index] -= 1
            if s1Count[index] == s2Count[index]:
                matches += 1
            elif s1Count[index] - 1 == s2Count[index]:
                matches -= 1
            l += 1
        return matches == 26

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$