Abstract / Summary

Find the most frequent substring of length k in a 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 53% (100k+ submissions).

Typical patterns to solve this problem:

• Hash Table
• Sliding Window
• String

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 implementation defines a method that determines the highest occurrence count of any substring whose length is at least minSize and at most maxSize, while also containing no more than maxLetters distinct characters. The core idea is a sliding-window traversal that maintains character frequencies for the current window and records qualifying substrings in a dictionary. By moving the window one character at a time, the algorithm avoids recomputing frequencies from scratch for overlapping substrings, which yields a linear-time scan of the input string.

Sliding-window initialization

seen = defaultdict(int)

left = 0
freq = defaultdict(int)

Two dictionaries are created. seen maps each qualifying substring to the number of times it appears; freq tracks the count of each character inside the current window. The left pointer marks the start of the window, while the loop variable right will serve as the end.

Expanding the window

for right, c in enumerate(s):
    # expand
    freq[c] += 1

During each iteration the character at position right is added to freq. This incremental update means the algorithm never recomputes the entire frequency map for the window; it only adjusts the count for the newly included character.

Checking the minimum size constraint

size = right - left + 1
if size < minSize:
    continue

If the window has not yet reached the required minimum length, the loop proceeds to the next character without further processing. This early-exit prevents unnecessary work for windows that cannot possibly satisfy the problem constraints.

Validating the distinct-letter limit

if len(freq) <= maxLetters:
    seen[s[left : right + 1]] += 1

When the window size meets minSize, the algorithm evaluates the number of unique characters by inspecting the length of freq. If the count does not exceed maxLetters, the current substring (from left to right, inclusive) is recorded in seen. Because the window slides one step at a time, each qualifying substring of length exactly minSize is counted.

Shrinking the window

freq[s[left]] -= 1
if freq[s[left]] == 0:
    del freq[s[left]]
left += 1

After processing the current window, the leftmost character is removed from freq. If its count drops to zero, the entry is deleted, which keeps freq compact and ensures that len(freq) accurately reflects the number of distinct characters. The left pointer is then advanced, preparing the window for the next iteration.

Result extraction

return max(seen.values()) if seen else 0

When the scan finishes, the method returns the largest occurrence count among all recorded substrings. If no substring satisfied the constraints, the function returns 0.

Edge-case handling

The code gracefully deals with several boundary conditions:

• Empty input string - The loop never executes, seen remains empty, and the final expression yields 0.
• minSize larger than the string length - The size check if size < minSize: continue prevents any substring from being recorded, again resulting in a return value of 0.
• maxLetters equal to 0 - Since len(freq) can never be less than or equal to 0 when a character is present, no substring is ever added to seen, leading to a 0 result.
• Repeated characters - When the window consists of a single repeated character, len(freq) stays at 1, satisfying the distinct-letter condition regardless of maxLetters (provided it is at least 1). The algorithm correctly counts each occurrence.
• Characters that disappear from the window - The deletion of a character from freq when its count reaches zero ensures that the distinct-letter count reflects the current window accurately, even when the same character appears, disappears, and reappears later.

Performance optimizations

The implementation incorporates several techniques that reduce overhead:

• Incremental frequency updates - By adjusting freq only for the entering and exiting characters, the algorithm avoids the O(window-size) recomputation that a naïve approach would incur.
• Dictionary pruning - Removing entries whose count drops to zero keeps freq small, which speeds up the len(freq) check and reduces memory pressure.
• Single-pass traversal - The sliding window moves forward exactly once, guaranteeing that each character is processed a constant number of times.
• Direct substring slicing - The slice s[left : right + 1] creates the substring only when the distinct-letter condition holds, preventing unnecessary string allocations for windows that fail the constraint.
• Conditional counting - The if seen else 0 guard avoids calling max on an empty sequence, which would raise an exception and require additional error handling.

Together, these choices ensure that the method runs efficiently even for long input strings while adhering strictly to the problem’s constraints.

Imagine you have a long string of colorful building blocks and you want to find the most popular patterns made of these blocks. This code acts like a little robot helper that slides a window over the blocks to look at small sections at a time. The robot keeps track of how many different kinds of colors are inside that window by using a special notebook called a dictionary.

The window starts at the left side of the block line and begins to grow toward the right. As the window grows, it remembers which blocks are inside. Once the window reaches a certain length, the robot checks its notebook to see if the colors inside are allowed. If the number of unique colors is small enough, the robot marks that specific pattern in another notebook to remember that it saw it.

After checking, the window shifts forward by moving its left side over, which means it drops the block that was at the very start of the group. This helps the window keep moving across the entire line of blocks until it hits the end. By doing this over and over, the robot finishes its job knowing exactly how many times it spotted each valid pattern.

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

not analyzed yet

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		Go	Rust	TS
	MemoryLimitExceeded	C++			Python
	Progiez	C++		Java	Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007				Python
	suxrobGM					C#
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java

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