Abstract / Summary

Count the number of ways to build strings of length n that avoid three consecutive identical characters using given building blocks.

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

Typical patterns to solve this problem:

• Dynamic Programming

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 combinatorial problem of counting binary strings whose lengths lie in the interval [low, high] and that can be constructed by repeatedly appending blocks of length zero (containing only ‘0’) or one (containing only ‘1’). The result is returned modulo 10⁹+7. The algorithm uses a one-dimensional dynamic programming (DP) array that records the number of ways to reach each possible total length up to high. After the DP table is filled, a final accumulation step sums the entries that fall within the required length range.

Key Steps

DP Table Initialization

The DP vector is sized to high + 1 and all entries are zeroed. The base case dp[0] = 1 represents the empty string, which serves as the starting point for building longer strings.

vector<int> dp(high + 1, 0);
dp[0] = 1;
const int MOD = 1000000007;

Iterative Transition

A single forward loop iterates over every length i from 0 to high-1. If dp[i] is zero the iteration is skipped, which avoids unnecessary work for unreachable lengths. For each reachable length, the algorithm attempts to extend the current string by a block of size zero and by a block of size one, provided the new length does not exceed high. The transition adds the number of ways to reach i to the target positions and applies the modulus to keep values bounded.

for (int i = 0; i < high; i++)
{
    if (dp[i] == 0)
        continue;

    if (i + zero <= high)
    {
        dp[i + zero] += dp[i];
        dp[i + zero] %= MOD;
    }

    if (i + one <= high)
    {
        dp[i + one] += dp[i];
        dp[i + one] %= MOD;
    }
}

Summation of Valid Lengths

After the DP table is complete, a second loop aggregates the counts for all lengths that satisfy the lower bound low. The accumulator is a 64-bit integer to prevent overflow before the final modulus operation.

int64_t sum = 0;
for (int i = low; i <= high; i++)
    sum += dp[i];

return sum % MOD;

Edge Cases Handled

The algorithm gracefully handles the situation where low is zero. Because dp[0] is initialized to one, the empty string is counted if the interval includes zero. When zero or one equals zero, the transition checks i + zero <= high and i + one <= high prevent infinite loops because the loop index i only advances forward; a zero-length block would never increase i, but the condition i + zero <= high would still be true, however the continue guard on dp[i] == 0 ensures that only reachable states propagate. If both block sizes are larger than high, the inner updates are never executed, leaving dp[0] as the sole non-zero entry, and the final sum correctly reflects that only the empty string (if within range) is valid.

When high is very large, the DP vector allocation respects the exact bound, and the modulus operation after each addition guarantees that intermediate values never exceed the 32-bit integer range, preventing overflow in the DP array itself.

Performance Optimizations

The implementation incorporates several practical optimizations:

• Sparse propagation guard - The if (dp[i] == 0) continue; statement skips work for lengths that cannot be formed, reducing the number of arithmetic operations especially when the reachable lengths are sparse.

• In-place modulus - By applying % MOD immediately after each addition, the algorithm avoids the need for a separate normalization pass and keeps the DP values within the range of a 32-bit signed integer, which improves cache friendliness.

• Single pass DP - The forward iteration from 0 to high-1 ensures that each state is processed exactly once, eliminating redundant recomputation that would arise in a recursive or memoized approach.

• Compact accumulator - Using a 64-bit accumulator only for the final summation isolates the larger integer arithmetic to a single loop, while the DP array itself remains 32-bit, reducing memory bandwidth.

These choices collectively yield a solution that runs in linear time with respect to high and uses linear additional space, while keeping the constant factors low through early exits and immediate modular reduction.

Imagine building a long tower using two different types of blocks. One type of block is a specific length called zero, and the other type is a different length called one. You want to see how many different ways you can build towers that are at least as tall as low but no taller than high.

The code works like a giant list of boxes where each box tells you how many ways there are to reach a certain height. You start at the very bottom, where height zero has one way to exist, because having nothing already counts as a way to start.

Then, the computer goes through every single height one at a time. It checks how many ways it already found to reach the current size. Once it knows that, it tries adding the zero block and the one block to see what new heights it can reach next. It keeps track of these counts as it goes, always making sure the numbers stay manageable by using a special math trick.

If it ever discovers a way to reach a height that fits perfectly between low and high, it tucks that number away. After checking all the possible heights up to the maximum limit, the computer adds up every way it found that fits your special range to tell you the final count.

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

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