MediumNo. 0567

Permutation in String — LeetCode 567 Python Solution

Topics
Hash Table, Two Pointers, String, Sliding Window
On a study list
NeetCode 150
Reading time
3 min

The problem

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

Input
s1 = "ab", s2 = "eidbaooo"
Output
true
Explanation
s2 contains one permutation of s1 ("ba").

Python solution

PythonSolution
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        cnt = Counter(s1)
        need = len(cnt)
        m = len(s1)
        for i, c in enumerate(s2):
            cnt[c] -= 1
            if cnt[c] == 0:
                need -= 1
            if i >= m:
                cnt[s2[i - m]] += 1
                if cnt[s2[i - m]] == 1:
                    need += 1
            if need == 0:
                return True
        return False

Complexity

Time
O(m + n), where m and n are the lengths of strings s1 and s2, respectively
Space · auxiliary
O(|Σ|), where Σ is the character set

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 567. Permutation in String is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 567. Permutation in String?

LeetCode 567. Permutation in String is rated Medium on LeetCode.

What is the time complexity of LeetCode 567. Permutation in String?

The Python solution on this page runs in O(m + n), where m and n are the lengths of strings \textit{s1} and \textit{s2}, respectively.

What is the space complexity of LeetCode 567. Permutation in String?

The Python solution on this page uses O(|Σ|), where \Sigma is the character set auxiliary space.

What topics does LeetCode 567. Permutation in String cover?

LeetCode 567. Permutation in String is tagged Hash Table, Two Pointers, String and Sliding Window on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.