Abstract / Summary

Check if one string can be formed by repeating the other string several times and joining them together.

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

Typical patterns to solve this problem:

• String
• String Matching

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 problem of determining the minimum number of times a string a must be concatenated with itself so that another string b becomes a substring of the resulting string. The algorithm proceeds by progressively extending a temporary string until it is guaranteed to be long enough to contain b, then checks for the presence of b. If the first check fails, a single additional copy of a is appended to cover the case where b straddles the boundary between two repetitions. The method returns the count of repetitions when successful, otherwise -1.

Key Steps

Building the minimal repeated string

The algorithm starts with a copy of a stored in aa and a counter result set to 1, representing the current number of repetitions. It then enters a loop that continues as long as the length of aa is less than the length of b. Inside the loop, another copy of a is concatenated to aa and the counter is incremented.

aa = a
result = 1
while len(aa) < len(b):
    aa += a
    result += 1

This step ensures that aa grows just enough to be at least as long as b. By stopping as soon as the length condition is satisfied, the algorithm avoids unnecessary concatenations.

First containment check

After the loop, the algorithm performs a direct substring test to see whether b already appears in the constructed aa. If the test succeeds, the current repetition count is returned immediately.

if b in aa:
    return result

This early exit handles the common situation where b fits entirely within the repeated copies built so far, eliminating further work.

Handling overlap across the concatenation boundary

If b is not found in the current aa, the algorithm anticipates the possibility that b may start near the end of aa and continue into the next copy of a. To capture this scenario, a single additional copy of a is appended, and the counter is incremented once more.

aa += a
result += 1

A second containment check follows. If b now appears, the updated repetition count is returned; otherwise, the method concludes that no amount of repetition will embed b and returns -1.

return result if b in aa else -1

Edge Cases Addressed

The logic explicitly covers several boundary conditions:

• When b is shorter than or equal to a, the initial loop may not execute, leaving aa equal to a single copy of a. The subsequent containment check then determines whether b is already a substring, handling the case where no repetition beyond the first is required.

• When b is longer than a, the loop repeats a enough times to reach at least the length of b. This guarantees that any possible alignment of b within the repeated string is examined.

• When b spans the junction between two copies of a, the extra concatenation after the first check ensures that the overlapping region is present in aa. The second containment test captures this situation, allowing the algorithm to return the correct count of repetitions.

• When b cannot be formed by any number of repetitions of a, the final return of -1 signals the impossibility after both containment checks have been exhausted.

Performance Optimizations

The implementation incorporates a few deliberate choices that improve runtime efficiency:

• The loop condition len(aa) < len(b) stops as soon as the temporary string reaches the length of b. This prevents the algorithm from building an excessively long string that would never be needed for the substring test.

• By performing an early containment check immediately after the loop, the method can often return without the extra concatenation, saving both time and memory for inputs where b fits within the minimal repeated prefix.

• The second concatenation is performed only once, regardless of how many repetitions were required to reach the length of b. This single additional copy is sufficient to cover any overlap scenario, avoiding a potentially unbounded number of further concatenations.

• The use of Python’s built-in substring operator in leverages highly optimized C-level routines for pattern searching, providing fast detection of b within aa without the need for custom scanning logic.

Imagine you have a long string of colorful stickers that spells out a word. You want to see if you can make a second, different word by lining up as many copies of the first sticker string as you need.

The first part of the code acts like a helper who keeps gluing more copies of the sticker string together until the chain is at least as long as the second word. It counts how many times the sticker string was added to the chain along the way.

Once the chain is long enough, the code checks if the second word is hidden inside that long chain of stickers. If it finds the word, the job is finished.

Sometimes the word might be split at the very edge where two copies of the sticker string meet. To make sure nothing is missed, the code adds one last copy of the sticker string to the chain. It takes one final look to see if the second word is there. If it is still not found after that, it means the word cannot be built no matter how many stickers are used.

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++		Java			Python		TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++		Java			Python	Go	TS
	LeetcodeHelp	C++		Java			Python
	Progiez	C++		Java			Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fengvyi	C++
	JoshCrozier		JS
	keineahnung2345	C++
	lkwq007						Python
	ruoru					Rust
	suxrobGM				C#
	varunu28			Java
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
varunu28	Java
zfang399	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