#567

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Permutation in String

Check if a string contains a permutation of another string using two-pointer scanning and hash table techniques.

hash table two pointers string sliding window

Problem Statement

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise. A permutation is any rearrangement of s1's characters.

For example, s1 = 'ab' and s2 = 'eidbaooo'. Since s2 contains a substring 'ba', which is a permutation of s1, the result is true. Otherwise, s2 may not have any valid permutations of s1.

Examples

Example 1

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

Output: true

s2 contains one permutation of s1 ("ba").

Example 2

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

Output: false

Example details omitted.

Constraints

1 <= s1.length, s2.length <= 104
s1 and s2 consist of lowercase English letters.

Solution Approach

Sliding Window with Hash Table

Use a sliding window of size equal to s1's length. Maintain a hash table to track the frequency of characters in the window. Move the window across s2, updating the hash table dynamically.

Two-Pointer Technique

By using two pointers to track the window's bounds and moving the window through s2, you can compare the frequency of characters in the current window with those in s1, without recalculating from scratch each time.

Efficient Comparison

Instead of repeatedly comparing full substrings, compare only the frequencies of characters. This reduces the time complexity to O(n), where n is the length of s2, ensuring the algorithm runs efficiently.

Complexity Analysis

Metric	Value
Time	O(l_1 + (l_2 - l_1)) \approx O(l_2)
Space	O(1)

The time complexity is O(l2), where l2 is the length of s2. The space complexity is O(1), as the hash table will store at most 26 characters for lowercase English letters.

What Interviewers Usually Probe

Can the candidate optimize the brute force approach?
Does the candidate demonstrate understanding of sliding window and hash table concepts?
Is the candidate able to explain the time complexity and avoid redundant operations?

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle character frequencies properly within the window.
Inefficiently recalculating the hash table for each new substring.
Failing to recognize the need for dynamic updates of the window.

Follow-up variants

Different constraints on the sizes of s1 and s2.
Handling strings with larger character sets (e.g., uppercase letters).
Modifying the problem to check for permutations in multiple substrings of s2.

FAQ

What is the optimal solution to the Permutation in String problem?

The optimal solution uses a sliding window approach combined with a hash table to track character frequencies and compare the window with the target string.

How does the sliding window help in solving this problem?

The sliding window allows you to examine each possible substring in s2 without recalculating character counts from scratch, leading to a more efficient solution.

Can brute force work for the Permutation in String problem?

Brute force may work, but it will lead to time limit exceeded (TLE) errors for large inputs. A sliding window approach is far more efficient.

What are the edge cases for the Permutation in String problem?

Edge cases include very short strings, strings where no permutation exists, or strings with identical characters.

What is the time complexity of the sliding window approach for this problem?

The time complexity is O(n), where n is the length of s2, since we scan through s2 just once while updating the window dynamically.

terminal

Solution

Solution 1: Sliding Window

We use an array $\textit{cnt}$ to record the characters and their counts that need to be matched, and a variable $\textit{need}$ to record the number of different characters that still need to be matched. Initially, $\textit{cnt}$ contains the character counts from the string $\textit{s1}$, and $\textit{need}$ is the number of different characters in $\textit{s1}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

Continue Practicing

#522 longest uncommon subsequence ii #438 find all anagrams in a string #424 longest repeating character replacement