Abstract / Summary

Check if any rearrangement of the first string appears as a substring inside the second string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 49% (3+ million submissions).

Typical patterns to solve this problem:

• Hash Table
• Sliding Window
• String
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation determines whether any permutation of the string s1 appears as a contiguous substring within s2. It follows a sliding-window strategy that maintains character frequency maps for the target window and compares them against the frequency map of s1. The algorithm returns True as soon as a matching window is found, otherwise it exhausts s2 and returns False.

Key Steps

Length Check

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

Before any processing, the code verifies that s1 cannot be longer than s2. If it is, a permutation is impossible, and the function exits early.

Building the Frequency Map for s1

freq1 = defaultdict(int)
for c in s1:
    freq1[c] += 1

A defaultdict of integers records how many times each character occurs in s1. This map serves as the reference for later comparisons.

Initial Window Construction

right = 0
freq2 = defaultdict(int)
while right < len(s1):
    freq2[s2[right]] += 1
    right += 1

The algorithm creates the first window in s2 whose length equals len(s1). The freq2 dictionary mirrors the character distribution inside this window, and the right pointer is positioned just beyond the window’s end.

Sliding the Window

left = 0
while True:
    if freq1 == freq2:
        return True

    if right == len(s2):
        return False

    if freq2[s2[left]] == 1:
        del freq2[s2[left]]
    else:
        freq2[s2[left]] -= 1

    freq2[s2[right]] += 1
    left  += 1
    right += 1

Inside an infinite loop, the code first checks whether the current window’s frequency map matches freq1. A match indicates that the current window is a permutation of s1, and the function returns True.

If the right pointer has reached the end of s2, no further windows can be formed, and the function returns False.

When advancing the window, the character leaving the window (at left) is decremented in freq2. If its count drops to zero, the entry is removed entirely, keeping the dictionary compact. The character entering the window (at right) is incremented. Both pointers are then moved one step forward, preserving the window size.

Final Return

return False

Although unreachable due to the loop’s return statements, this line satisfies the function’s signature.

Edge Cases Handled

The early length comparison gracefully handles the scenario where s1 is longer than s2.

When a character’s count in the sliding window becomes zero, the code deletes the key from freq2. This ensures that the equality check (freq1 == freq2) does not produce a false negative due to lingering zero-count entries.

The loop’s termination condition (right == len(s2)) correctly stops processing when the window has been slid to the very end of s2, covering the case where the last possible window does not match.

Performance Optimizations

The algorithm avoids recomputing the entire frequency map for each window. By updating only the two characters that change as the window slides (the outgoing and incoming characters), it achieves constant-time updates per iteration.

Removing zero-count entries from freq2 keeps the dictionary size minimal, which speeds up the equality comparison between freq1 and freq2.

Using defaultdict(int) eliminates the need for explicit existence checks before incrementing or decrementing counts, reducing branching overhead.

The early exit when a match is found prevents unnecessary traversal of the remainder of s2.

Overall, the design leverages a tight sliding-window mechanism with incremental updates, yielding an efficient solution for the permutation-in-string problem.

Imagine you have a big bucket full of letter magnets and a smaller bag that also has letter magnets inside. The goal here is to see if you can find exactly all the same letters from the small bag hiding inside a little section of the big bucket.

First, the code checks to see if the bag is bigger than the bucket. If the bag has more letters than the bucket, it is impossible for them to fit, so the search stops before it even starts.

Next, a tiny inventory list is made to count how many of each letter are in the small bag. Then, another count is made for the first group of letters in the bucket, just matching the size of the small bag.

Now comes the fun part which acts like a sliding window. The window moves across the bucket one letter at a time. Every time the window moves, one letter from the back is taken out and a new letter from the front is added in. After each slide, the code compares the inventory list of the small bag with the current inventory list of the window. If the lists match perfectly, it means the letters from the bag are hiding in that spot. If the window reaches the end of the bucket and no match is found, the search finishes.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python						TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python	Rust		Go	C#		TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	begeekmyfriend								C
	BigEggStudy							C#
	black-shadows	C++
	bujosa				Rust
	chandansgowda			Python
	charles-wangkai		Java
	everthis					JS
	fengvyi	C++
	fpdjsns	C++
	gouthampradhan		Java
	halfrost						Go
	JoshCrozier					JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007			Python
	muhammadfarhankt						Go
	ruoru				Rust
	sonugiri1043	C++
	suxrobGM							C#
	trung-hn			Python
	varunu28		Java
	vli02								C
	vthwang		Java
	withaarzoo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java, Python
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
fpdjsns	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
muhammadfarhankt	Go
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
withaarzoo	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality