Permutation in String

Sliding WindowHash Map

20 min

Problem Statement

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise. In other words, return true if one of s1's permutations is the substring of s2.

Example

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"

s1: "ab"

s2: "eidbaooo"

Output: true

("ba" is a permutation of "ab" and a substring of "eidbaooo")

Output: true

Solution

We can use a sliding window approach with a hash map (or an array as a frequency map) to solve this problem. The core idea is to maintain a window of the same size as `s1` and check if the character counts in the window match the character counts of `s1`.

Algorithm Steps

Create a frequency map for `s1`.
Initialize a sliding window of size `s1.length` in `s2`.
Create a frequency map for the initial window.
If the frequency maps match, return `true`.
Slide the window one character at a time:
- Add the new character to the window's frequency map.
- Remove the character that's leaving the window from the frequency map.
- Check if the frequency maps match. If they do, return `true`.
If the end of `s2` is reached and no match is found, return `false`.

Permutation in String Visualization

Sliding Window Approach

Progress1 / 1

Ready to start the visualization

s1 Frequency Map

Window Frequency Map

Permutation in String Solution


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):
            if s1Count[i] == s2Count[i]:
                matches += 1

        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