Permutation in String

Medium

📘 Problem Statement

Given two strings s1 and s2, return true if s2 contains any permutation of s1 as a substring, else return false.

s1 and s2 consist of lowercase English letters.

🔍 Example

s1 = "ab", s2 = "eidbaooo" ➝ true
Explanation: s2 contains "ba", which is a permutation of s1.

s1 = "ab", s2 = "eidboaoo" ➝ false

---

Intuition

• A permutation of a string is simply a rearrangement of its characters.

• We need to find a substring in s2 of length = len(s1) that has the same character counts as s1.

🛠️ Solution

💡 Approach: Sliding Window + Frequency Map

1. Fixed-size sliding window:

• The length of the window should be equal to the length of s1.

• Slide the window through s2, one character at a time.

1. Frequency counter:

Keep two frequency arrays (size 26 if only lowercase letters):

• s1_count: frequency of characters in s1

• window_count: frequency of characters in current window in s2

1. Compare the two counters:

• If at any point s1_count == window_count, return true.

🧑‍💻 Code

def checkInclusion(s1: str, s2: str) -> bool:
    from collections import Counter

    len1, len2 = len(s1), len(s2)

    if len1 > len2:
        return False

    s1_count = [0] * 26
    s2_count = [0] * 26

    for i in range(len1):
        s1_count[ord(s1[i]) - ord('a')] += 1
        s2_count[ord(s2[i]) - ord('a')] += 1

    # First window comparison
    if s1_count == s2_count:
        return True

    # Slide the window over s2
    for i in range(len1, len2):
        s2_count[ord(s2[i]) - ord('a')] += 1
        s2_count[ord(s2[i - len1]) - ord('a')] -= 1

        if s1_count == s2_count:
            return True

    return False

🕒 Time Complexity: \(O(N)\), where N = length of s2 characters early. 📦 Space Complexity: \(O(1)\) — Frequency arrays are of constant size (26)