Abstract / Summary

Given a string, find the length of the longest substring where all characters are the same after replacing at most k characters.

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 60% (2+ million 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 provided implementation solves the classic “longest substring with at most k replacements” problem using a sliding-window technique. It maintains a dynamic window over the input string s, expands the window to the right while tracking character frequencies, and contracts from the left whenever the number of characters that would need to be replaced exceeds the allowed limit k. The variable result records the maximum window length observed, which corresponds to the length of the longest feasible substring.

Core Logic

Initialization

result = 0
have = defaultdict(int)
left = 0

result stores the best answer found so far. have is a dictionary that counts occurrences of each character inside the current window. left marks the start index of the window.

Expanding the Window

for right, c in enumerate(s):
    have[c] += 1
    dominant = max(have.values())

The loop iterates over each character c with its index right. The count for c is incremented, and dominant captures the frequency of the most common character in the window. This value determines how many characters are already aligned with the optimal replacement target.

Computing Window Viability

length   = right - left + 1
other    = length - dominant

length is the current window size. other represents the number of characters that differ from the dominant character and would therefore need to be replaced. The window is valid when other does not exceed k.

Shrinking When Necessary

if other > k:
    have[s[left]] -= 1
    left   += 1
    length -= 1

If the required replacements exceed k, the leftmost character is removed from the window, its count is decremented, and left advances. Adjusting length reflects the new window size after contraction.

Updating the Result

result = max(result, length)

After each iteration, result is updated with the larger of its current value or the present window length, ensuring that the longest feasible window is retained.

Final Return

return result

The function concludes by returning the maximum length discovered.

Edge Cases Handled

When the input string is empty, the loop body never executes, leaving result at its initial value of 0, which correctly represents the length of the longest possible substring.

If k is larger than or equal to the length of s, the condition other > k never triggers, allowing the window to expand over the entire string; consequently, result becomes the full length of s.

The algorithm also gracefully handles strings consisting of a single repeated character. In that scenario, dominant equals length at every step, making other zero, so the window never contracts and result grows to the full string length.

When k is zero, the window can only contain characters that are already identical. The code continuously shrinks the window whenever a differing character appears, effectively tracking the longest run of identical characters.

Performance Optimizations

The implementation leverages a single pass over the input string, updating the frequency map incrementally. By maintaining dominant as the maximum count in the current window, it avoids recomputing the entire frequency distribution for each possible replacement target.

The use of defaultdict(int) eliminates the need for explicit existence checks before incrementing or decrementing character counts, streamlining the update operations.

Adjusting length directly after a contraction avoids recomputing the window size from scratch in subsequent steps, saving a constant amount of work per iteration.

Overall, the algorithm achieves an efficient balance between simplicity and speed, processing each character exactly once while keeping auxiliary data structures minimal.

Imagine a long train of colorful blocks stretching out in front of you. Some blocks are red, some are blue, and some are green. The goal is to make the longest possible train where every block is the exact same color, but there is one special rule. You are allowed to use a handful of magic wands to change any block you want into any color you choose. You have a fixed number of these magic wands to use.

To solve this, the code looks at a section of the train at a time. It uses two markers to show the start and the end of the section being inspected. As the marker at the end moves forward, the block it lands on gets added to a list that keeps track of how many blocks of each color are in that section. It looks at the list to see which color shows up the most because it is easier to change the other colors to match the most popular one. Then, it checks if the number of blocks that need to be changed fits within the limit of magic wands.

If the number of blocks that need a magic wand is more than what is available, the section is too big to be all one color. To fix this, the marker at the start of the section slides forward one spot and removes that block from the list of counted colors. This keeps the section small enough to be manageable. Throughout this whole process, the code keeps track of how long the section is and remembers the biggest length it has found so far. By the time the marker at the end reaches the very last block, the largest section of same-colored blocks has been found.

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					Go			Python	TS
	LeetcodeHelp	C++	Java								Python
	MemoryLimitExceeded	C++									Python
	Progiez	C++	Java								Python
github	black-shadows	C++
	bujosa			Rust
	charles-wangkai		Java
	everthis				JS
	fartem					Ruby
	fsq	C++
	halfrost							Go
	JoshCrozier				JS
	keineahnung2345	C++
	linouk23	C++
	MacJim	C++
	ruoru			Rust
	sonugiri1043	C++
	suxrobGM								C#
	varunu28		Java
	vli02									C
	vthwang		Java
	wisdompeak	C++
	yuanliu666						Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
black-shadows	C++, C++
bujosa	Rust
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
MacJim	C++
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
yuanliu666	Kotlin
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