459. Repeated Substring Pattern (Easy)

Problem

Given a string s, return True if it can be constructed by taking a substring of it and appending multiple copies of the substring together. Return False otherwise.

Example

s = "abab" → True ("ab" repeated twice)
s = "aba" → False
s = "abcabcabcabc" → True ("abc" repeated four times)

LeetCode 459 · Link · Easy

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Approach 1: Try all divisor lengths

A repeated pattern of length p can only work if p divides n = len(s). Try every valid period length and check.

Python
TypeScript

def repeated_substring_pattern(s: str) -> bool:
    n = len(s)                                   # L1: O(1)
    for p in range(1, n // 2 + 1):              # L2: loop, n/2 iterations
        if n % p != 0:                           # L3: O(1) divisibility check
            continue
        if s[:p] * (n // p) == s:               # L4: O(n) build + compare
            return True                          # L5: O(1)
    return False                                 # L6: O(1)

function repeatedSubstringPattern(s: string): boolean {
    const n = s.length;                                   // L1: O(1)
    for (let p = 1; p <= Math.floor(n / 2); p++) {       // L2: loop, n/2 iterations
        if (n % p !== 0) continue;                        // L3: O(1) divisibility check
        if (s.slice(0, p).repeat(n / p) === s) return true; // L4: O(n) build + compare
    }
    return false;                                         // L6: O(1)
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L1 (length)	$O(1)$	1	$O(1)$
L2 (loop)	$O(1)$	n/2	$O(n)$
L3 (mod check)	$O(1)$	n/2	$O(n)$
L4 (build + compare)	$O(n)$	up to n/2	$O(n^2)$ ← dominates
L5, L6 (returns)	$O(1)$	1	$O(1)$

The string construction s[:p] * (n // p) allocates and fills a string of length n, then the == comparison scans all n characters. Done at up to n/2 positions, that is $O(n^2)$ total.

Complexity

Time: $O(n^2)$ , driven by L4 (the $O(n)$ build-and-compare inside an $O(n)$ loop).
Space: $O(n)$ for the constructed candidate string at each step.

Swift

final class Solution {
    func repeatedSubstringPattern(_ s: String) -> Bool {
        let chars = Array(s)
        if chars.count < 2 { return false }
        for length in 1...(chars.count / 2) where chars.count % length == 0 { if String(repeating: String(chars[0..<length]), count: chars.count / length) == s { return true } }
        return false
    }
}

Approach 2: The (s + s)[1:-1] trick

If s is built from a repeating pattern, then doubling it (s + s) and removing the first and last characters still contains s somewhere in the middle. If s is not a repeated pattern, removing those boundary characters breaks any interior copy.

Python
TypeScript

def repeated_substring_pattern(s: str) -> bool:
    doubled = (s + s)[1:-1]    # L1: O(n) concatenate and slice
    return s in doubled         # L2: O(n) substring search

function repeatedSubstringPattern(s: string): boolean {
    const doubled = (s + s).slice(1, -1);  // L1: O(n) concatenate and slice
    return doubled.includes(s);            // L2: O(n) substring search
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L1 (s + s then slice)	$O(n)$	1	$O(n)$
L2 (substring search)	$O(n)$	1	$O(n)$ ← dominates

Python’s in operator for strings uses an optimized search (similar to Boyer-Moore-Horspool). Both lines are $O(n)$ .

Complexity

Time: $O(n)$ , driven by L1/L2 (linear string operations).
Space: $O(n)$ for doubled.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Why this works

Suppose s = "abab" (pattern "ab" repeated twice).

s + s = "abababab"
(s + s)[1:-1] = "bababab"

Does "abab" appear in "bababab"? Yes, at index 1.

Now suppose s = "aba" (not a repeated pattern):

s + s = "abaaba"
(s + s)[1:-1] = "baab"

Does "aba" appear in "baab"? No. Correctly returns False.

Removing the first character breaks the leading copy of s; removing the last breaks the trailing copy. Any remaining occurrence of s must be an internal one, which only exists when s is genuinely periodic.

Note: with KMP for the substring search inside L2, the full algorithm is $O(n)$ with no hidden constant. See KMP for details.

Swift

final class Solution {
    func repeatedSubstringPattern(_ s: String) -> Bool {
        guard s.count > 1 else { return false }; let doubled = s + s; return doubled.dropFirst().dropLast().contains(s)
    }
}

Summary

Approach	Time	Space
Try all divisors	$O(n^2)$	$O(n)$
(s+s)[1:-1] trick	$O(n)$	$O(n)$

Test cases

Python
TypeScript

# Quick smoke tests, paste into a REPL or save as test_459.py and run.
# Uses Approach 2.

def repeated_substring_pattern(s: str) -> bool:
    return s in (s + s)[1:-1]

def _run_tests():
    assert repeated_substring_pattern("abab") == True
    assert repeated_substring_pattern("aba") == False
    assert repeated_substring_pattern("abcabcabcabc") == True
    assert repeated_substring_pattern("a") == False
    assert repeated_substring_pattern("aa") == True
    assert repeated_substring_pattern("abaaba") == True
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function assert(condition: boolean, msg: string = ''): void {
    if (!condition) throw new Error(msg || 'Assertion failed');
}

function repeatedSubstringPattern(s: string): boolean {
    return (s + s).slice(1, -1).includes(s);
}

assert(repeatedSubstringPattern("abab") === true);
assert(repeatedSubstringPattern("aba") === false);
assert(repeatedSubstringPattern("abcabcabcabc") === true);
assert(repeatedSubstringPattern("a") === false);
assert(repeatedSubstringPattern("aa") === true);
assert(repeatedSubstringPattern("abaaba") === true);
console.log("all tests pass");

KMP algorithm, $O(n)$ substring search used inside approach 2
Find the Index of the First Occurrence in a String, substring search problem

Math and Number Theory, the arithmetic invariant behind digits, divisibility, modulo behavior, and identities.
Array Scans, the linear pass habit of carrying just enough state while reading each item once.