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(|\Sigma|), 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.

Permutation in String — LeetCode 567 Python Solution

MediumHash TableTwo PointersStringSliding Window

Problem: #567
Pattern: Sliding Window
Reading time: 3 min
Source: leetcode.com

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

Python

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

Measure	Complexity
Time	O(m + n), where m and n are the lengths of strings \textit{s1} and \textit{s2}, respectively
Space	O(\|\Sigma\|), where \Sigma is the character set auxiliary

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.

On a study list

This problem is on NeetCode 150.

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(|\Sigma|), 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.