LeetCode: 567 Permutation in String

LeetCode 567: Permutation in String

Problem Description:
Given two strings s1 and s2, write a function to check if s2 contains a permutation of s1. In other words, check if there exists a substring in s2 that is an anagram of s1.

Code Implementation:

from collections import Counter

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

        # If s1 is longer than s2, it's impossible for s2 to contain a permutation of s1
        if n1 > n2:
            return False

        # Create frequency counters for s1 and the initial window in s2
        count_s1 = Counter(s1)
        window = Counter(s2[:n1])

        # Check the initial window
        if count_s1 == window:
            return True

        # Slide the window across s2
        for i in range(n1, n2):
            window[s2[i]] += 1  # Add the new character to the window
            window[s2[i - n1]] -= 1  # Remove the character that leaves the window

            # Remove the character if its count becomes 0 to match the behavior of Counter
            if window[s2[i - n1]] == 0:
                del window[s2[i - n1]]

            # If the window matches count_s1, we found a permutation
            if count_s1 == window:
                return True

        return False

Problem Analysis

The task is to find a substring in s2 that matches any permutation of s1.
This problem can be solved using the sliding window technique combined with frequency counting.

Solution Explanation

1. Length Check

if n1 > n2:
    return False

If the length of s1 is greater than s2, it’s clear that s2 cannot contain a permutation of s1, so we return False immediately.

2. Frequency Counters

Use Counter to keep track of the frequency of characters in s1 and the initial window of s2.

3. Initial Window Check

if count_s1 == window:
    return True

If the initial window of s2 matches the frequency count of s1, return True.

4. Sliding Window Iteration

Start sliding the window over s2 from index n1.
For each new character, add it to the current window’s frequency count.
Remove the character that has just moved out of the window.
If a character’s count reaches 0, delete it from the window to ensure the counts match precisely.

5. Return Result

If we find a matching window during the iteration, return True. If no matching window is found by the end, return False.

Complexity Analysis

Time Complexity: O(n1 + n2)
- Creating the initial frequency counter takes O(n1).
- Sliding the window takes O(n2 – n1).
- Thus, the overall time complexity is O(n1 + n2).
Space Complexity: O(1)
- The Counter size is bounded by the number of unique characters, which is at most 26 for lowercase letters.

Example Explanation

Example 1

Input: s1 = "ab", s2 = "eidbaooo"
Output: True
Explanation: The substring "ba" in s2 is a permutation of s1.

The initial window is "ei", which doesn’t match.
As the window slides, it becomes "id", "db", and then "ba", where "ba" matches a permutation of s1.

Example 2

Input: s1 = "ab", s2 = "eidboaoo"
Output: False
Explanation: There is no permutation of s1 in s2.

After sliding the window through the entire string, no matching permutation is found.

Summary

This solution efficiently uses the sliding window and frequency counter to solve the problem.
It has a time complexity of O(n1 + n2), making it suitable for large inputs.

Post Views: 49

CODEBITWAVE