Abstract / Summary

Given a string and a list of substrings to remove repeatedly until none remain, find the shortest possible string length.

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 77% (300k+ submissions).

Typical patterns to solve this problem:

• Simulation
• Stack
• 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 defines a class Solution with a single method minLength. The method receives a string s and repeatedly removes every occurrence of the substrings "AB" and "CD" until no further removals are possible. The final length of the string after all possible deletions is returned as an integer. The algorithm relies on Python’s built-in str.replace method to perform the deletions in a loop that terminates when the string length stabilizes.

Key Steps

The core of the algorithm is a while loop that continues as long as the length of the string changes between iterations. The loop body consists of two replacement operations that eliminate the target patterns.

while result != len(s):
    result = len(s)
    s = s.replace("AB", "")
    s = s.replace("CD", "")

The loop condition compares a stored length (result) with the current length of s. At the start of each iteration result is updated to the length observed before any replacements. The two replace calls then produce a new version of s with all "AB" and "CD" substrings removed. After the replacements, the loop condition is re-evaluated; if the length has decreased, another pass is performed.

When the loop exits, the method returns the stabilized length.

return result

Edge Cases Handled

The algorithm naturally accommodates several edge conditions without additional logic:

• Empty Input - If s is an empty string, the initial length is zero, the loop condition fails immediately, and the method returns zero.
• String Without Target Substrings - When s contains no "AB" or "CD" sequences, the first iteration leaves s unchanged, causing the loop condition to be false after the first check, and the original length is returned.
• Overlapping Patterns - Because str.replace processes non-overlapping occurrences from left to right, overlapping patterns such as "ABC" are handled correctly: the "AB" part is removed, leaving "C" which may later combine with adjacent characters to form a new "AB" or "CD" in subsequent iterations.
• Consecutive Removals - Situations where removal of one pattern creates a new instance of another pattern are covered by the loop’s repeated passes. For example, the string "ABCD" becomes "CD" after the first replacement, and a second pass removes "CD" entirely, resulting in an empty string.
• Large Repetitive Sequences - Strings composed of many repeated "AB" or "CD" substrings shrink dramatically in each iteration, and the loop continues until all such substrings are exhausted.

Performance Optimizations

The implementation leverages Python’s highly optimized C-level string handling for the replace operation. By calling replace twice per iteration, the code avoids manual scanning or character-by-character manipulation, which would be slower in pure Python. The use of a length comparison (result != len(s)) as the loop guard eliminates the need for an explicit flag to detect changes, allowing the loop to terminate precisely when the string stabilizes.

Because each replace call creates a new string, the algorithm benefits from Python’s internal memory management that reuses buffers when possible, reducing allocation overhead for successive iterations. The approach also minimizes the number of passes over the data: each iteration processes the entire current string only twice, regardless of its size, and the loop terminates as soon as no further deletions are possible, preventing unnecessary work.

Imagine the letters inside the computer are playing a game of tag. The computer looks through a long string of these letters to find two specific pairs. One pair is A followed by B, and the other pair is C followed by D. When the computer spots one of these pairs, it quickly takes those two letters out of the string and tosses them away, just like clearing toys off the floor.

Because taking those letters out might push two other letters together to form a new pair, the computer keeps checking the string over and over again. It keeps picking up and removing the pairs until there are no more hidden A followed by B or C followed by D combinations left to find. Once the string is as tidy as it can possibly get with no more pairs to remove, the computer stops working and counts how many letters are left sitting there.

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

Time: polynomial
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	Java				C++	Python	TS
	WalkCCC	Java				C++	Python
	leetcode.ca	Java	Rust	JS	Go	C++	Python	TS
	Progiez	Java				C++	Python
github	charles-wangkai	Java
	fsq		Rust
	JoshCrozier			JS
	varunu28	Java
	withaarzoo				Go
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	Rust
JoshCrozier	JavaScript
varunu28	Java
withaarzoo	Go

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