A-018● Day 182026.05.20mediumleetcode #567neetcode150

Permutation in String

#hash-table#two-pointers#string#sliding-window

Problem

· problem

P.018

Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise. In other words, return true if one of s1's permutations is the substring of s2.

constraints

· 1 ≤ s1.length, s2.length ≤ 10⁴
· s1 and s2 consist of lowercase English letters

// paraphrased summary — see source for full text

examples

example 1input → output

"ab"
"eidbaooo"

true

example 2input → output

"ab"
"eidboaoo"

false

Pre-solve

· pre-solve

● 1list shown→● 2select→● 3reveal

☐
Does order matter in a permutation?
☐
Why maintain two separate frequency arrays?
☐
What does the 'matches' variable count?
☐
Why does the main loop start at r = len(s1)?
☐
Would sorting each substring be faster?
☐
Is the early exit 'if matches == 26' strictly necessary?
☐
If s1 = 'ab' and s2 = 'aba', should the function return true?

check the items you would ask, then press confirm

// session-only state — refresh resets (repeatable practice)

Logic Structure

· logic

● 1slots shown→● 2pick per slot→● 3reveal

// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.

step 1· Boundary Check: Length Validation

○

if len(s1) > len(s2):

○

if len(s1) >= len(s2):

○

if len(s1) < len(s2): return False

step 2· Initialize Frequency Arrays and First Window

○

s1Count, s2Count = [0] * 26, [0] * 26

○

s1Count, s2Count = [0] * 25, [0] * 25

○

s1Count = [0] * 26  # s2Count는 없음

step 3· Count Initial Character Matches│ nested

○

matches += 1 if s1Count[i] == s2Count[i] else 0

○

matches += 1 if s1Count[i] != s2Count[i] else 0

○

# 초기 matches 계산을 건너뜀

step 4· Main Sliding Window Loop

○

for r in range(len(s1), len(s2)):

○

for r in range(len(s1)):

○

for r in range(len(s2)):

step 5· Add Character at Right and Update Matches│ nested

○

s2Count[index] += 1

○

s2Count[ord(s2[r]) - ord('a')] += 1

○

if s1Count[index] == s2Count[index] - 1:
    matches += 1
s2Count[index] += 1

step 6· Remove Character at Left and Update Matches│ nested

○

s2Count[index] -= 1

○

s2Count[ord(s2[l]) - ord('a')] -= 1
l += 1

○

s2Count[ord(s2[l]) - ord('a')] -= 1
# l += 1이 없음

pick one option per slot

// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.

Solve · Trace

· solve

solution.py

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

mental dry-run cases

// walk each case in your head; expand the worked example below if stuck.

case 1

"ab"
"eidbaooo"

→

true

case 2

"ab"
"eidboaoo"

→

false

// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.