LeetCode 567: Permutation In String — Step-by-Step Visual Trace

#leetcode #python #algorithms

Medium — Sliding Window | Hash Table | String | Two Pointers

The Problem

Given two strings s1 and s2, return true if s2 contains a permutation of s1. A permutation is a rearrangement of characters, so we need to find if any substring of s2 has the same character frequencies as s1.

Approach

Use a sliding window technique with two hash maps to track character frequencies. Maintain a window of size len(s1) in s2, comparing the character frequency of the current window with s1's frequency map. Slide the window by adding the right character and removing the left character.

Time: O(n) · Space: O(k)

Code

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False

        char_freq_s1 = {}
        for char in s1:
            char_freq_s1[char] = char_freq_s1.get(char, 0) + 1

        left, right = 0, 0
        char_freq_temp = {}

        while right < len(s2):
            char_freq_temp[s2[right]] = char_freq_temp.get(s2[right], 0) + 1

            if right - left + 1 == len(s1):
                if char_freq_temp == char_freq_s1:
                    return True
                char_freq_temp[s2[left]] -= 1
                if char_freq_temp[s2[left]] == 0:
                    del char_freq_temp[s2[left]]
                left += 1

            right += 1

        return False