LeetCode 567: Permutation in String Solution in Python – A Step-by-Step Guide

What Is LeetCode 567: Permutation in String?

In LeetCode 567: Permutation in String, you’re given two strings s1 and s2, and your task is to return True if s2 contains a substring that is a permutation of s1—meaning it has the same characters with the same frequencies, in any order—and False otherwise. For example, with s1 = "ab" and s2 = "eidbaooo", s2 contains "ba," a permutation of "ab," so return True. This problem builds on LeetCode 438: Find All Anagrams in a String for substring matching but focuses on finding just one valid permutation.

Problem Statement

• Input: s1 (str)—target string; s2 (str)—source string to search in.
• Output: Boolean—True if s2 contains a permutation of s1, False otherwise.
• Rules: Permutation means same character counts; substring must be contiguous.

Constraints

• 1 <= s1.length, s2.length <= 10⁴
• s1 and s2 consist of lowercase English letters.

Examples

• Input: s1 = "ab", s2 = "eidbaooo"
• Output: True
• Substring "ba" in "eidbaooo" is a permutation of "ab".
• Input: s1 = "ab", s2 = "eidboaoo"
• Output: False
• No contiguous substring matches "ab"’s frequency.
• Input: s1 = "hello", s2 = "ooolleoooeh"
• Output: False
• No substring has "hello"’s exact character count.

Understanding the Problem: Finding a Permutation

To solve LeetCode 567: Permutation in String in Python, we need to determine if s2 contains a contiguous substring of the same length as s1 with identical character frequencies, indicating it’s a permutation of s1. With lengths up to 10⁴, a brute-force approach generating all permutations of s1 and searching for each (O(n! * m)) is impractical. Instead, we can use a sliding window to efficiently compare frequency counts in O(m) time, where m is s2’s length. We’ll explore:

• Best Solution (Sliding Window with Frequency Counting): O(m) time, O(1) space—fast and optimal.
• Alternative Solution (Brute-Force Permutation Checking): O(n! * m) time, O(n) space—simple but slow (n = s1 length, m = s2 length).

Let’s dive into the sliding window solution with a friendly breakdown!

Best Solution: Sliding Window with Frequency Counting

Why Sliding Window Wins

The sliding window with frequency counting is the best for LeetCode 567 because it efficiently checks for a permutation in O(m) time and O(1) space (since the alphabet is fixed at 26 lowercase letters) by sliding a fixed-size window over s2, maintaining character frequencies, and comparing them to s1’s frequencies in constant time per step. It’s like sliding a magnifying glass over the string, checking each section for a perfect character match—all in one swift pass!

How It Works

Think of this as a window-sliding detective:

• Step 1: Initialize Frequencies:
• Create frequency arrays (or dictionaries) for s1 and the first window of s2 (size = s1 length).
• Step 2: Check First Window:
• Compare frequencies; if match, return True.
• Step 3: Slide Window:
• For each step:
• Remove leftmost character (decrement its count).
• Add new rightmost character (increment its count).
• Check if frequencies match s1’s.
• Step 4: Return Result:
• True if match found, False if end reached without match.
• Why It Works:
• Permutations have identical frequency counts.
• Sliding window avoids recomputing full counts.

It’s like a frequency-matching sleuth!

Step-by-Step Example

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

• Step 1: Initialize:
• s1 freq: {'a': 1, 'b': 1}.
• Window (0-1): "ei" → {'e': 1, 'i': 1}.
• Step 2: First window mismatch.
• Step 3: Slide window:
• (1-2): Remove 'e', add 'd': "id" → {'i': 1, 'd': 1}, mismatch.
• (2-3): Remove 'i', add 'b': "db" → {'d': 1, 'b': 1}, mismatch.
• (3-4): Remove 'd', add 'a': "ba" → {'b': 1, 'a': 1}, match! Return True.
• Result: True.

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

• Step 1: s1 freq: {'a': 1, 'b': 1}.
• Step 2: Window "ei": {'e': 1, 'i': 1}, mismatch.
• Step 3: Slide:
• "id": {'i': 1, 'd': 1}, mismatch.
• "db": {'d': 1, 'b': 1}, mismatch.
• "bo": {'b': 1, 'o': 1}, mismatch.
• "oa": {'o': 1, 'a': 1}, mismatch.
• "ao": {'a': 1, 'o': 1}, mismatch.
• "oo": {'o': 2}, mismatch.
• Step 4: No match, end reached.
• Result: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        # Step 1: Check if s1 is longer than s2
        if len(s1) > len(s2):
            return False

        # Step 2: Initialize frequency arrays (26 lowercase letters)
        s1_count = [0] * 26
        window_count = [0] * 26
        for char in s1:
            s1_count[ord(char) - ord('a')] += 1

        # Step 3: Fill first window
        for i in range(len(s1)):
            window_count[ord(s2[i]) - ord('a')] += 1
        if s1_count == window_count:
            return True

        # Step 4: Slide window and check
        for i in range(len(s1), len(s2)):
            # Remove leftmost character
            window_count[ord(s2[i - len(s1)]) - ord('a')] -= 1
            # Add new rightmost character
            window_count[ord(s2[i]) - ord('a')] += 1
            if s1_count == window_count:
                return True

        # Step 5: No match found
        return False

• Lines 4-5: If s1 longer than s2, impossible.
• Lines 8-11: Count s1 frequencies (a-z).
• Lines 14-17: Count first window, check match.
• Lines 20-25: Slide window:
• Decrement left character.
• Increment right character.
• Check match.
• Line 28: Return False if no match.
• Time Complexity: O(m)—single pass over s2.
• Space Complexity: O(1)—fixed 26-letter arrays.

It’s like a window-sliding matchmaker!

Alternative Solution: Brute-Force Permutation Checking

Why an Alternative Approach?

The brute-force permutation checking generates all permutations of s1 and searches for each in s2, running in O(n! * m) time and O(n) space (n = s1 length, m = s2 length). It’s simple but impractical for larger strings, making it a good baseline for small inputs or understanding.

How It Works

Picture this as a permutation-hunting seeker:

• Step 1: Generate all permutations of s1.
• Step 2: Check if each is a substring of s2.
• Step 3: Return True if any found, False otherwise.

It’s like a permutation-probing explorer!

Step-by-Step Example

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

• Step 1: Permutations: ["ab", "ba"].
• Step 2: Check:
• "ab" in "eidbaooo" → False.
• "ba" in "eidbaooo" → True.
• Result: True.

Code for Brute-Force Approach

Copy codefrom itertools import permutations

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

        # Generate all permutations of s1
        perms = [''.join(p) for p in permutations(s1)]

        # Check each permutation in s2
        for perm in perms:
            if perm in s2:
                return True

        return False

• Lines 5-6: Check length feasibility.
• Line 9: Generate permutations.
• Lines 12-14: Check each as substring.
• Line 16: Return False if no match.
• Time Complexity: O(n! * m)—permutations times substring check.
• Space Complexity: O(n)—permutation storage.

It’s a brute-force permutation checker!

Comparing the Two Solutions

• Sliding Window (Best):
• Pros: O(m), O(1), fast.
• Cons: Frequency logic.
• Brute-Force (Alternative):
• Pros: O(n! * m), O(n), simple.
• Cons: Impractical for large n.

Sliding window wins for efficiency!

Additional Examples and Edge Cases

• s1 = "a", s2 = "a": True`.
• s1 = "abc", s2 = "cba": True`.
• s1 = "abc", s2 = "def": False`.

Sliding window handles them all!

Complexity Recap

• Sliding Window: Time O(m), Space O(1).
• Brute-Force: Time O(n! * m), Space O(n).

Sliding window’s the speed champ!

Key Takeaways

• Sliding Window: Frequency finesse—learn at Python Basics!
• Brute-Force: Permutation probe.
• Strings: Permutations are fun.
• Python: Slide or brute, your pick!

Final Thoughts: Spot That Permutation!

LeetCode 567: Permutation in String in Python is a clever string challenge. Sliding window with frequency counting is your fast track, while brute-force offers a thorough dive. Want more? Try LeetCode 438: Find All Anagrams or LeetCode 76: Minimum Window Substring. Ready to match? Head to Solve LeetCode 567 on LeetCode and find that permutation today!