LeetCode #459 Easy

Repeated Substring Pattern

Decide whether a string can be built by repeating some substring block two or more times.

stringstring-matching

02

Intuition

💡

The trap is testing every possible candidate length from 1 up to the full string, or only checking half the string and calling it done. Neither is necessary: if a block of length L is going to tile the string evenly, L must DIVIDE len(s) exactly -- any length that doesn't divide evenly can never repeat to fill the string, so you can skip it without even trying. That cuts the candidates down to just the divisors of len(s). There's also a slick one-liner worth knowing: s is built from a repeating block exactly when s shows up inside (s+s) with the first and last characters removed -- that trick exists because concatenating s with itself and trimming the ends only preserves a match if there was genuine periodicity, not just the trivial wraparound.

03

Approach

1

Only check divisors of the length

Loop candidate block lengths L from 1 up to len(s)//2. For each L, first check whether len(s) % L == 0; if it doesn't divide evenly, skip immediately without building anything.

2

Rebuild and compare

For a length that does divide evenly, take the first L characters as the candidate block, repeat it len(s)//L times, and compare the rebuilt string against s. If they match, the string is periodic with that block and you can return True right away.

3

Fall through to false

If no divisor length produces a match, the string does not decompose into a repeated block, so return False. This also naturally handles length-1 strings, which have no valid L <= len(s)//2.

04

Solution & live demo

python

▶1class Solution:
▶2    def repeatedSubstringPattern(self, s: str) -> bool:
▶3        n = len(s)
▶4        for length in range(1, n // 2 + 1):
▶5            if n % length != 0:
▶6                continue
▶7            block = s[:length]
▶8            if block * (n // length) == s:
▶9                return True
▶10        return False

05

Edge cases

string of length 1

no candidate length <= len(s)//2 exists, loop doesn't run, returns False

length is prime

only L=1 could divide it before len(s)//2, but a single repeated character rarely matches unless all chars are equal

whole string is one repeated character

L=1 divides and rebuilding matches immediately

length divides by multiple factors

smallest matching L is found first since the loop goes in increasing order

06

Complexity

Time

O(n^2) worst case

Space

O(n)

each candidate rebuild-and-compare is O(n); only divisors of n are tried