Abstract / Summary

Check if a string contains a substring of length m that repeats k or more times in a row.

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 44% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Enumeration

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 Solution class implements a method containsPattern that determines whether a given integer array arr contains a repeating sub-pattern of length m that occurs consecutively at least k times. The algorithm iterates over possible starting positions in the array and checks, for each candidate, whether the segment of length m repeats the required number of times without exceeding the array bounds. If any such pattern is found, the method returns True; otherwise it returns False.

Key Steps

Iterating Over Potential Start Indices

The outermost loop selects each index a in the array as a possible beginning of the repeating pattern.

for a in range(len(arr)):
    ok = True
    ...

By scanning from the first element to the last, the algorithm ensures that every feasible start position is examined.

Scanning the Pattern Length

Inside the outer loop, a second loop iterates over the m positions that constitute the candidate pattern. The variable b represents the offset within the pattern relative to the start index a.

for b in range(m):
    offset = a + b
    ...

The calculation of offset aligns the current element of the pattern with its position in the original array.

Verifying Repetitions Across k Blocks

For each offset, a third loop checks the element against its counterparts in the subsequent k repetitions. The index pos computes the location of the element in the c-th repetition block.

for c in range(k):
    pos = offset + m * c
    if pos >= len(arr) or arr[offset] != arr[pos]:
        ok = False
        break

The condition pos >= len(arr) prevents out-of-range access, effectively handling the edge case where the remaining array length is insufficient to accommodate the full k repetitions. If any mismatch is detected, the flag ok is cleared and the inner loops terminate early.

Early Exit on Successful Detection

After the inner loops finish without clearing ok, the method returns True immediately, indicating that a valid repeating pattern has been found.

if ok:
    return True

This early exit avoids unnecessary further scanning once the required condition is satisfied.

Final Result When No Pattern Exists

If the outer loop exhausts all start positions without finding a matching pattern, the method concludes that the array does not contain the specified repetition and returns False.

return False

Edge Cases Handled

The algorithm gracefully manages several boundary situations:

• When m is larger than the remaining length of the array from a given start index, the inner check pos >= len(arr) will trigger, preventing out-of-bounds reads and marking the candidate as invalid.
• When k equals zero, the inner repetition loop executes zero times, leaving ok unchanged; the outer logic then treats any start index as a valid pattern, which aligns with the interpretation that zero repetitions impose no constraint.
• When the array is empty, the outer loop does not execute, and the method returns False, correctly indicating that no pattern can exist.
• When m or k are one, the loops reduce to simple equality checks, and the code still correctly validates the presence of a single element repeated once or more.

Performance Optimizations Observed

The implementation incorporates two notable efficiency techniques:

• Early Termination on Mismatch: As soon as a discrepancy is found between the reference element arr[offset] and any of its expected repetitions, the inner loops break out, and the flag ok is set to False. This prevents needless comparisons for the remaining repetitions of the current pattern candidate.
• Immediate Return on Success: Upon confirming a valid pattern, the method returns True without continuing the outer iteration. This short-circuiting eliminates further work once the answer is known.

These optimizations reduce the average number of element comparisons, especially in cases where mismatches occur early in the pattern or where a valid pattern is located near the beginning of the array.

Imagine a long train of colored blocks lined up in a row. This code is like a little robot helper that wants to find a special repeating pattern hidden somewhere in that line. The robot starts at the very beginning of the train and looks at a small group of blocks. It remembers what those blocks look like and then jumps ahead to check if the exact same group of blocks shows up again right after the first one.

The robot keeps jumping forward to see if the group repeats enough times to match the goal. If the robot finds the pattern repeating over and over just like it needs to, it smiles because the mission is a success. If it gets to the end of the line and finds out the pattern never finished repeating, it just moves to the next spot in the train to try again with a brand new starting point. It looks at every single spot in the line one by one until the work is finished.

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++	Python	Java					TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java				Go	TS
	Progiez	C++	Python	Java
github	black-shadows	C++
	charles-wangkai			Java
	fartem				Ruby
	FelixFan1122			Java
	fsq	C++
	JoshCrozier					JS
	keineahnung2345	C++
	lkwq007		Python
	suxrobGM						C#
	trung-hn		Python
	varunu28			Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fartem	Ruby
FelixFan1122	Java
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

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