Abstract / Summary

Find the shortest binary string that contains all substrings from 1 to n as consecutive bits.

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

Typical patterns to solve this problem:

• 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 with a single method that determines whether every integer from 1 up to a given limit appears as a binary substring inside a supplied string. The algorithm mixes a deterministic check for the smallest values with a probabilistic sampling for the remainder, returning a Boolean result.

Key Steps

The method begins by declaring a helper function that converts an integer to its binary representation (without the leading “0b”) and checks for its presence in the input string.

def find(n):
    b = bin(n)[2:]
    return s.find(b) != -1

The first major phase iterates over the initial segment of the range, bounded by either the limit n or the constant 100, whichever is smaller. For each value the helper is invoked; a missing binary pattern triggers an immediate False return.

for i in range(1, min(n + 1, 100)):
    if not find(i):
        return False

If the deterministic loop completes without failure, the algorithm proceeds to a stochastic phase. It performs a fixed number of trials-one thousand-each time selecting a random integer between 1 and n. The same helper validates the presence of the corresponding binary substring; any failure again yields False.

for i in range(1000):
    r = randint(1, n)
    if not find(r):
        return False

When both phases finish without encountering a missing pattern, the method concludes that the condition holds for the sampled space and returns True.

return True

Edge Cases Handled

The deterministic loop gracefully handles situations where the upper bound n is less than the constant 100. By using min(n + 1, 100) the range automatically adjusts, ensuring that the loop never exceeds the actual limit and that no unnecessary checks are performed.

The helper function safely processes the integer 0, although the outer loops start at 1, thereby avoiding any unintended behavior with a zero value.

When n is exactly 1, the deterministic loop checks the single required binary pattern, and the random sampling phase still executes a thousand trials with randint(1, 1), which always yields 1. This redundancy confirms the presence of the sole required substring without error.

If the input string s is empty, the helper’s find call will always return -1, causing the first missing pattern to be detected immediately and the method to return False. This early exit prevents unnecessary computation.

The use of randint(1, n) respects the inclusive bounds of the random selection, guaranteeing that every possible integer in the target range has a non-zero probability of being sampled during the stochastic phase.

Performance Optimizations

The implementation leverages Python’s built-in str.find method, which is implemented in C and provides fast substring search compared to a manual scan. By converting each integer to its binary form once per check, the code avoids repeated string construction within the search operation.

Limiting the exhaustive verification to the first hundred integers dramatically reduces the worst-case work for large values of n. This deterministic segment ensures that the most common small numbers, which are more likely to be missing, are verified thoroughly.

The subsequent random sampling introduces a probabilistic shortcut: instead of iterating over the entire remaining range, the algorithm performs a fixed number of checks (one thousand). This approach caps the runtime regardless of how large n becomes, while still providing a high probability of detecting a missing pattern if one exists.

Early termination is built into both loops. As soon as a binary substring is not found, the method returns False without completing the remaining iterations. This short-circuit behavior prevents wasted work once a failure is detected.

By combining a small deterministic window with a bounded stochastic probe, the code balances thoroughness for low-index values against scalability for high-index ranges, achieving a practical trade-off between accuracy and execution time.

Every number can be written as a secret code made just of ones and zeros. If the number one is written as one, the number two is written as one zero, and the number three is written as one one. This code looks at a long string of letters and symbols to see if it can find the secret code for every number from one all the way up to a target number.

First, the code makes a list of the first hundred numbers to check if their secret codes are hiding inside the string. It looks through the string to see if the ones and zeros match up. If even one of those numbers is missing, it stops and says the goal was not reached.

After checking those first numbers, the code decides to play a game of hide and seek. It picks one thousand random numbers between one and the target number and checks each one to see if its secret code is in the string. If it finds a missing number during this game, it says the goal was not reached. If it finishes checking all those numbers and finds them all, it confirms that everything needed was inside the string the whole time.

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