Abstract / Summary

Check if the string can be made by repeating a shorter substring multiple times.

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 48% (1+ million 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 determines whether a given string can be constructed by repeating one of its substrings. It iterates over possible substring lengths (referred to as stride) and checks if the entire string consists of repetitions of the candidate substring. The function returns true as soon as a valid repeating pattern is found; otherwise it returns false after exhausting all candidates.

Core Logic

Enumerating Candidate Substring Lengths

The outer loop selects each possible stride from 1 up to half of the string length. A stride larger than half cannot repeat because at least two copies are required.

for (auto stride = 1; stride <= s.size() / 2; stride++)
{
    if (s.size() % stride != 0)
        continue;
    // ...
}

The modulo check discards lengths that do not evenly divide the total length, because a repeating pattern must tile the string without leftovers.

Verifying a Candidate Pattern

For a stride that passes the divisibility test, the algorithm validates the pattern by comparing characters positioned stride apart. Two nested loops perform this verification. The outer inner loop iterates over the positions within the first candidate block, while the inner inner loop walks through the rest of the string in steps of stride.

bool ok = true;
for (auto i = 0; i < stride && ok; i++)
    for (auto j = i + stride; j < s.size() && ok; j += stride)
        if (s[i] != s[j])
            ok = false;

The ok flag short-circuits both loops as soon as a mismatch is detected, preventing unnecessary comparisons.

Early Success Return

If the verification completes without setting ok to false, the function concludes that the string is composed of repeated substrings and returns true immediately.

if (ok)
    return true;

Default Failure Return

When no stride yields a successful verification, the function reaches the final statement and returns false.

return false;

Edge Cases Handled

The algorithm gracefully handles an empty input string. Since the outer loop’s upper bound becomes zero, the loop body never executes and the function returns false, indicating that an empty string does not satisfy the repeating-substring condition.

A single-character string also bypasses the outer loop because s.size() / 2 evaluates to zero. Consequently, the function returns false, reflecting that a solitary character cannot be formed by repeating a shorter substring.

Strings whose lengths are prime numbers are automatically excluded from further checks for any stride that does not divide the length, because the modulo condition eliminates all non-divisible candidates. This prevents futile verification attempts.

When the string consists of identical characters (e.g., "aaaa"), the first stride that divides the length (in this case 1) passes the verification quickly, and the function returns true after minimal work.

Performance Optimizations

The implementation incorporates several techniques that reduce the amount of work performed:

• Divisibility Pre-filter - By checking s.size() % stride != 0 before any character comparison, the algorithm avoids entering the verification loops for strides that cannot possibly tile the string.

• Flag-Based Loop Short-Circuit - The ok boolean controls both inner loops. As soon as a mismatch is found, ok becomes false, causing the loop conditions && ok to fail and halting further comparisons for the current stride.

• Early Return on Success - The moment a valid repeating pattern is identified, the function exits with true. This prevents the exploration of larger strides that are unnecessary once a solution is known.

• Limited Search Space - The outer loop only iterates up to s.size() / 2. This bound eliminates redundant checks for strides that would require more than one repetition, thereby shrinking the candidate set.

• Incremental Comparison Pattern - By comparing characters at positions i and i + stride, i + 2*stride, etc., the algorithm reuses the characters from the first block as a reference, eliminating the need to construct or store the candidate substring explicitly.

These choices collectively keep the runtime proportional to the amount of necessary character comparison, avoiding extra memory allocations and redundant passes over the input.

Imagine you have a long train made of colored blocks, and you want to know if the whole train is just the same tiny group of blocks repeating over and over again.

The code starts by picking a small length for a potential pattern. It tries the smallest length first, which is one block long. It checks if the whole train can be divided perfectly into pieces of that size. If it cannot, the code skips to the next size because a pattern must fit neatly without leaving any leftover blocks.

Once a size is chosen, the code looks at the very first piece of the pattern and compares it to all the other pieces that come later. It checks the first block of every repeating section to see if they all have the exact same color. If it finds even one spot where the colors do not match, the code knows this size is not a repeating pattern. It then moves on to try the next, slightly larger size.

The process continues until the code either finds a size that repeats perfectly throughout the entire train or runs out of sizes to test. If a repeating pattern is discovered, everything is a success. If it gets to the end without finding any pattern that works, then the train does not repeat.

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

Time: polynomial
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	C++	Java	Python								TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python				Rust			Go	TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	fartem								Ruby
	gouthampradhan		Java
	JoshCrozier				JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007			Python
	martianoff						Scala
	ruoru							Rust
	suxrobGM					C#
	varunu28		Java
	vli02									C
	wisdompeak	C++
	YuriSpiridonov			Python
	zfang399	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
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
gouthampradhan	Java
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
martianoff	Scala
ruoru	Rust
suxrobGM	C#
varunu28	Java
vli02	C
wisdompeak	C++
YuriSpiridonov	Python
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