Abstract / Summary

You must create the longest possible string using only a and b without having three a or three b in a row.

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

Typical patterns to solve this problem:

• Greedy
• 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 strWithout3a3b. The method receives two integer parameters, a and b, representing the desired counts of characters 'a' and 'b' in the output string. The goal is to construct a string that contains exactly a occurrences of 'a' and b occurrences of 'b' while never allowing three consecutive identical characters. The algorithm builds the result incrementally, making decisions based on the current suffix of the partially constructed string and the remaining counts of each character.

Key Steps

The core of the algorithm is a loop that continues as long as either a or b is greater than zero. Inside the loop, three decision points guide the choice of the next character.

The first decision checks whether the current result ends with two 'a' characters. If it does, the algorithm appends a 'b' and decrements b. This prevents the formation of three consecutive 'a' characters.

if result.endswith("aa"):
    result += "b"
    b -= 1
    continue

The second decision mirrors the first, looking for a suffix of two 'b' characters. When such a suffix is found, a single 'a' is appended and a is decremented, thereby avoiding three 'b' characters in a row.

if result.endswith("bb"):
    result += "a"
    a -= 1
    continue

If neither of the above suffix conditions applies, the algorithm compares the remaining counts of 'a' and 'b'. When more 'a' characters remain than 'b', an 'a' is added; otherwise a 'b' is added. This heuristic tends to balance the distribution of characters while respecting the count constraints.

if a > b:
    result += "a"
    a -= 1
else:
    result += "b"
    b -= 1

After the loop terminates, the fully constructed string is returned.

return result

Edge Cases Handled

The code gracefully handles the situation where one of the character counts reaches zero before the other. Because the loop condition checks a > 0 or b > 0, the algorithm continues to add the remaining characters of the non-zero type. The suffix checks (endswith("aa") and endswith("bb")) ensure that even when only one character type is left, the algorithm will not violate the three-in-a-row rule. For example, if a becomes zero while b is still positive, the suffix check will insert an 'a' only when two 'b's are already present, thereby breaking a potential triple of 'b'. Conversely, when b is exhausted, the same logic prevents three consecutive 'a's.

Another subtle edge case is the initial state where the result string is empty. Neither suffix condition matches, so the algorithm falls back to the count comparison. This correctly chooses the character with the larger remaining count as the first character, establishing a balanced start.

Performance Optimizations

The implementation avoids unnecessary data structures; it builds the output directly in a mutable string variable result. By using result.endswith checks, the algorithm inspects only the last two characters of the current string, which is an O(1) operation in Python because string slicing for a fixed small length does not depend on the overall string size. The use of continue statements after handling a forced character insertion prevents the execution of the subsequent comparison logic within the same iteration, reducing the number of conditional evaluations per loop cycle.

The decision to decrement the appropriate counter immediately after appending a character ensures that the loop invariant (remaining counts accurately reflect the characters still needed) is maintained without extra bookkeeping. This tight coupling of state update and character addition eliminates the need for a separate tracking structure, contributing to a lean runtime profile.

Imagine putting together a long train made of blocks. You have two buckets of blocks, one filled with blocks labeled a and one filled with blocks labeled b. The goal is to build a long chain using all of these blocks, but there is a special rule that says no more than two of the same letter can ever stand next to each other.

The computer starts with an empty space and looks at the buckets. It checks to see if the end of the train already has two a blocks sitting together. If that happens, the computer knows it must pick a b block next to keep things safe. The exact same logic applies if there are two b blocks at the end, because then the computer knows it must pick an a block to stop them from touching too much.

If the train is not in any danger of having three blocks in a row, the computer looks at which bucket has more blocks left. It picks a block from the bucket with the most leftovers. This way, the piles stay balanced and the train keeps growing until every single block has been used and joined to the line. The computer keeps repeating these steps over and over until the buckets are completely empty.

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