Here is solution for Permutation in String.

1. Understanding the problem

• Given two strings s1 and s2, determine if any permutation of s1 is a substring of s2. Return True if there exists a contiguous substring of s2 that is a permutation of s1, otherwise False.

• Special cases:

  • Empty s1: I’ll treat len(s1) == 0 as True (vacuously a permutation). This can be adjusted to interviewer preference.

  • Do not seperate by the case lowercase English letters

2. Clarifying questions

1. Are characters limited to lowercase English letters?

2. What should we return on empty inputs?

3. Expected time/space complexity?, aim for O(n) time and O(1) extra space => Maybe we should use hashmap for this (use hashmap for case duplicate ‘a’: 2, ‘b’: 1).

3. Work through examples

1. s1 = “ab”, s2 = “eidbaooo” → True (“ba” appears).

2. s1 = “ab”, s2 = “eidboaoo” → False (no substring perm).

3. s1 = “aa”, s2 = “aaaa” → True (“aa” appears many places).

4. s1 = “”, s2 = “anything” → True (by our convention).

5. s1 = “xyz”, s2 = “xy” → False (s1 longer than s2).

6. Danger-case: repeated characters and mixed order: s1=”aab”, s2=”eidbaaoo” → True (“baa” or “aba” possible).

=> Because substring we use sliding window, but not only hash map or hash set.

4. Brainstorm 2–3 solutions (with complexities)

4.1. Brute-force permutations + search

• Generate every permutation of s1 (k! permutations), check if any is substring of s2.

• Time: O(k! * n) — impractical except tiny k.

• Space: O(k) per permutation.

4.2. Sliding window + frequency comparison

• Maintain frequency map of s1 (need) and sliding window frequency of current window in s2 of length k = len(s1).

• Naive map comparison is O(k) per slide → O(n*k).

=> But we can maintain a matches counter (count how many characters have matched required frequency) to get O(n) time

Notes:

• We can optimize it to O(N) => Because we insert each time when we traverse the character, or remove left when it exceed k => time to insert O(1).

• And we can change it to a string to convert each key of the map => O(26 * N).

5. Implement solutions

5.1. Brute Force - O(N klogk)

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

        for i in range(len(s2)):
            for j in range(i, len(s2)):
                subStr = s2[i : j + 1]
                subStr = sorted(subStr)
                if subStr == s1:
                    return True
        return False

• Time complexity: O(N^3 logN).

• Space complexity: O(N).

Notes: We can optimize to only look for substring with length k.

5.2. Hash Table - O(N * K)

• Using the counter to verify when match => O(N * M), where M is the number of length of S1.

• If count1 have more character than count2, it means we can continue.

• If count1 have smaller character than count2 => we use exceed the base of count1 => break and init new count.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        count1 = {}
        for c in s1:
            count1[c] = 1 + count1.get(c, 0)

        need = len(count1)
        for i in range(len(s2)):
            count2, cur = {}, 0
            for j in range(i, len(s2)):
                count2[s2[j]] = 1 + count2.get(s2[j], 0)
                if count1.get(s2[j], 0) < count2[s2[j]]:
                    break
                if count1.get(s2[j], 0) == count2[s2[j]]:
                    cur += 1
                if cur == need:
                    return True
        return False

*- Time: O(N* M).

• Space: O(1), since the key we use at most 26 characters.*

5.3. Easy to implement O(26 * N)

def checkInclusion_lowercase(s1: str, s2: str) -> bool:
    """
    Assumes s1 and s2 contain only lowercase letters 'a'..'z'.
    Returns True if some permutation of s1 is a substring of s2.
    """
    n1, n2 = len(s1), len(s2)
    if n1 == 0:
        return True
    if n1 > n2:
        return False

    cnt1 = [0]*26
    cnt2 = [0]*26
    base = ord('a')

    for ch in s1:
        cnt1[ord(ch) - base] += 1
    for ch in s2[:n1]:
        cnt2[ord(ch) - base] += 1

    if cnt1 == cnt2:
        return True

    for i in range(n1, n2):
        # include s2[i], exclude s2[i - n1]
        cnt2[ord(s2[i]) - base] += 1
        cnt2[ord(s2[i - n1]) - base] -= 1
        if cnt1 == cnt2:
            return True

    return False

5.4. Sliding Window - O(N)

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

        s1Count, s2Count = [0] * 26, [0] * 26
        for i in range(len(s1)):
            s1Count[ord(s1[i]) - ord('a')] += 1
            s2Count[ord(s2[i]) - ord('a')] += 1

        matches = 0
        for i in range(26):
            matches += (1 if s1Count[i] == s2Count[i] else 0)

        l = 0
        for r in range(len(s1), len(s2)):
            if matches == 26:
                return True

            index = ord(s2[r]) - ord('a')
            s2Count[index] += 1
            if s1Count[index] == s2Count[index]:
                matches += 1
            elif s1Count[index] + 1 == s2Count[index]:
                matches -= 1

            index = ord(s2[l]) - ord('a')
            s2Count[index] -= 1
            if s1Count[index] == s2Count[index]:
                matches += 1
            elif s1Count[index] - 1 == s2Count[index]:
                matches -= 1
            l += 1
        return matches == 26

• Time: O(N).

• Space: O(26).

• Idea:

  • Find the matches first k digits.

  • If continue to match, match += 1, if before add s2 match, but after add s1 it do not match more => match -= 1.

  • Compare total matches == 26 return true, else False.

=> Instead of compare 26 * N each time query => use match variable for N items.