Abstract / Summary

Check if a string is valid by repeatedly replacing every three consecutive 'b's with a single 'b' until no more can be replaced.

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

Typical patterns to solve this problem:

• 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 isValid method determines whether a given string composed of the characters a, b, and c follows a strict ordering rule. The rule requires that every b must be immediately preceded by an a, and every c must be immediately preceded by the sequence ab. The method processes the input sequentially, using a list as a stack to keep track of pending characters, and returns True only when the entire string satisfies the ordering constraints and the stack is empty at the end.

Key Steps

Stack initialization

The algorithm begins by creating an empty list that serves as a stack for tracking characters that have not yet been matched.

incomplete = []  # stack

Iterating through the input

A for loop walks through each character in the input string, allowing the method to react to each symbol in turn.

for c in s:

Processing an a

When the current character is a, it is simply added to the stack, indicating that a potential ab pair has started.

if c == "a":
    incomplete.append(c)

Processing a b

For a b, the method first checks that the stack is not empty and that the most recent unmatched character is an a. If either condition fails, the string is invalid and the method returns False. When the checks succeed, the b is pushed onto the stack, marking the continuation of a valid ab sequence.

elif c == "b":
    # stack must be preceded by "a"
    if not incomplete:
        return False
    if incomplete[-1] != "a":
        return False
    incomplete.append(c)

Processing a c

A c requires that the two most recent unmatched characters on the stack be b followed by a. The method verifies that at least two elements exist, then pops and checks them in order. If the expected pattern is not present, the string is rejected. Successful verification removes the matched ab pair from the stack, completing a valid abc segment.

else:  # c == "c"
    # stack must be preceded by "ab"
    if len(incomplete) < 2:
        return False
    if incomplete.pop() != "b":
        return False
    if incomplete.pop() != "a":
        return False

Final validation

After the loop finishes, the method returns True only if the stack is empty, meaning every a and b has been correctly paired with a subsequent c.

return not incomplete

Edge Cases Handled

The implementation gracefully handles an empty input string; the loop body never executes, leaving the stack empty, and the final return yields True. Strings that start with b or c trigger the early-return checks because the stack will be empty or insufficiently populated, resulting in False. Sequences that contain extra a or b characters without a matching c leave residual entries on the stack, causing the final not incomplete test to fail. Likewise, a stray c that does not follow an ab pair is caught by the length check and the subsequent pop validations, ensuring that only properly ordered triples are accepted.

Performance Optimizations

The algorithm employs early exits at the first sign of a rule violation, preventing unnecessary processing of the remainder of the string. By using a Python list as a stack, append and pop operations execute in constant time, keeping the runtime overhead minimal. The checks for stack emptiness and top-element validation are performed before any modifications, avoiding redundant work. The final not incomplete test provides a single, inexpensive verification step to confirm that all characters have been successfully matched.

Imagine you have a row of colorful building blocks and a special magic box. This code plays a game with three letters: a, b, and c.

When the code sees the letter a, it picks it up and puts it into the magic box. Think of this like putting a toy into a storage bin.

When the code sees the letter b, it first checks inside the magic box to make sure there is an a waiting there. If it finds one, it puts the b into the box right on top of the a. It is very important that b stays close to its friend a.

When the code sees the letter c, it needs to find both a and b. It looks inside the magic box and pulls out the b, and then it pulls out the a. The code wants to make sure that the b and a are ready and waiting in the right order before it finishes with the c.

After looking at all the letters, the code checks to see if the magic box is totally empty. If everything was paired up perfectly and there are no stray blocks hiding in the box, then the game is finished successfully.

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