Given a string s, decide whether it can be built by repeating one of its substrings several times.
def repeatedSubstringPattern(s):
return s in (s + s)[1:-1]
If s is a repetition of a block p, shifting s by len(p) gives s again, so a copy of s appears inside s + s at a position other than 0 or len(s). Cutting the first and last characters removes exactly those two trivial matches. Conversely, a nontrivial match means s equals a rotation of itself, which forces a period that divides len(s).
def repeatedSubstringPattern(s):
n = len(s)
for L in range(1, n // 2 + 1):
if n % L == 0 and s[:L] * (n // L) == s:
return True
return False
This is O(n * d(n)) where d(n) is the number of divisors, fine for interview limits.
If you want to rehearse explaining solutions like this under time pressure, an interview copilot is something I help build (disclosure: I work on Linkjob AI).
Further reading: Linkjob AI resource directory