Abstract / Summary

You must build the longest string by picking characters from given strings while keeping their order.

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

Typical patterns to solve this problem:

• Dynamic Programming
• Greedy
• Math

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 public method longestString. The method receives three integer parameters x, y, and z, which represent the available counts of three distinct letter groups. The algorithm builds the longest possible string under a set of transition rules that restrict which group may follow another. The core of the solution is a depth-first search with memoization that explores all feasible sequences of “chunks”, where each chunk consists of two characters. The final answer is twice the number of chunks found, because each chunk contributes exactly two letters to the resulting string.

Core Logic

Transition Rules

The comments at the top of the method describe the allowed state transitions between the three groups:

x => y
y => x or z
z => x or z

These rules are encoded in the recursive helper deeper. The helper receives four arguments:

• wasDoubleA - a Boolean flag indicating whether the previous chunk was of type “AA”.
• aa - remaining count of group x (the “A” group).
• bb - remaining count of group y (the “B” group).
• ab - remaining count of group z (the “AB” group).

The flag determines which transitions are legal from the current state. When wasDoubleA is true, the only permissible next chunk is “AB”, which consumes one unit from bb. When the flag is false, the algorithm may choose either an “AA” chunk (consuming one from aa) or an “AB” chunk (consuming one from ab). This directly mirrors the transition diagram described in the comment.

Recursive Exploration

The inner function deeper is decorated with @cache, which automatically memoizes results for each unique combination of its arguments. This eliminates redundant recomputation of sub-problems and ensures that each state is evaluated at most once.

The body of deeper initializes a local variable result to zero. The subsequent conditional blocks update result by adding one for the current chunk and recursively calling deeper with the updated counts and appropriate flag value. The use of max when both “AA” and “AB” options are available guarantees that the longest continuation from the current state is retained.

The relevant snippet:

@cache
def deeper(wasDoubleA, aa, bb, ab):
    result = 0
    if wasDoubleA:                     # previous chunk was "AA"
        if bb > 0:
            result = 1 + deeper(False, aa, bb - 1, ab)
    else:                              # previous chunk was "AB" or "BB"
        if aa > 0:
            result = 1 + deeper(True, aa - 1, bb, ab)
        if ab > 0:
            result = max(result, 1 + deeper(False, aa, bb, ab - 1))
    return result

Entry Points

The outer method longestString initiates the search from three possible starting chunks, each corresponding to using one unit of one of the three groups. For each non-zero count, it calls deeper with the appropriate flag and decremented count. The maximum of these three starting possibilities is stored in result.

result = 0
if x > 0:
    result = 1 + deeper(True, x - 1, y, z)
if y > 0:
    result = max(result, 1 + deeper(False, x, y - 1, z))
if z > 0:
    result = max(result, 1 + deeper(False, x, y, z - 1))

Finally, the method returns 2 * result because each recursive step counted a chunk of two characters.

Edge Cases Handled

The algorithm explicitly checks for the availability of each group before attempting to consume a unit. When any of the counts x, y, or z is zero, the corresponding branch is skipped, preventing attempts to decrement a negative count. Inside deeper, the conditions if bb > 0, if aa > 0, and if ab > 0 guard against underflow, ensuring that the recursion only proceeds when a valid chunk can be formed. This design naturally handles cases where one or more groups are exhausted early, causing the recursion to terminate and return zero for that path.

When both aa and ab are zero while wasDoubleA is false, the function reaches the base case with result remaining zero, correctly indicating that no further chunks can be added. Similarly, when wasDoubleA is true and bb is zero, the function also returns zero, reflecting the impossibility of extending the sequence under the transition constraints.

Performance Optimizations

The most significant optimization is the use of Python’s built-in functools.cache decorator on the recursive helper. By caching the return value for each distinct tuple (wasDoubleA, aa, bb, ab), the algorithm avoids exponential blow-up typical of naïve depth-first searches. Since the state space is bounded by the product of the three input counts plus the Boolean flag, the memoization ensures that each state is processed exactly once.

Another subtle optimization is the early pruning of impossible moves through the guard conditions (if bb > 0, etc.). By checking resource availability before making recursive calls, the function prevents the creation of cache entries for invalid states, reducing the overall number of stored entries.

The final multiplication by two (2 * result) is performed only once after the recursive exploration, avoiding repeated arithmetic inside the recursion and keeping the inner loop focused solely on counting chunks.

Summary of Execution Flow

The method begins by evaluating each possible starting chunk, invoking the memoized recursive helper with the appropriate flag and decremented counts. The helper explores all legal continuations, always choosing the longest path from the current state. Memoization guarantees that overlapping sub-problems are solved a single time. Once the deepest reachable state is found for each entry point, the outer method selects the maximum chunk count, doubles it, and returns the length of the longest string that satisfies the transition rules.

Imagine you have a big bucket full of letter tiles. Some tiles have AA written on them, some have BB, and some have AB. The goal is to lay them down in a long line, but there is one special rule. You are not allowed to put two of the same tile next to each other if they look the same. For example, if you just put down AA, the next tile cannot be an AA. You have to pick something that starts with a different letter, like a BB or an AB.

The code works like a very careful organizer. When it decides which tile to put down next, it checks the rule to make sure the game stays fun. It starts by looking at every possible tile you could pick first. Then, it calls a helper function that looks at the pile again to see what could come next given the rule. If the function sees that the last tile was an AA, it knows it must pick a tile starting with B. If the last tile was an AB or a BB, it has more choices and can pick either an A or a B.

To make sure the game goes as long as possible, the code keeps track of all the different ways to line up the tiles using that clever memory trick called cache. This keeps it from having to do the same thinking twice. Since every single tile choice is actually a pair of letters, once the organizer finds the longest sequence of tiles possible, it multiplies that number by two to count every single letter in the line.

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