Log inSign up
easyleetcodeNot Started

Repeated Substring Pattern

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Example 1:

Input: s = "abab"
Output: true
Explanation: It is the substring "ab" repeated twice.

Example 2:

Input: s = "aba"
Output: false
Explanation: Cannot be constructed by repeating any substring.

Example 3:

Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" repeated four times or "abcabc" repeated twice.

Constraints:

  • 1 <= s.length <= 104
  • s consists of lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Prove string periodicity via KMP LPS.
  • Master the doubled-string rotation search trick.
  • Understand the mathematical relationship between prefix-suffix overlap and fundamental periods.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Determining whether a sequence is formed by repeating a smaller unit.
  • Finding the minimum repeating period of a string.

Algorithmic Decision Tree:

  • Determining whether a sequence is formed by repeating a smaller unit.
  • Finding the minimum repeating period of a string.

Connected Patterns:

Longest Prefix SuffixKMP Pattern MatchingRotate String

1. Divisor Substring Testing

Intuition

For each possible pattern length L from 1 to N / 2: if N % L == 0, extract sub = s.substr(0, L). Repeat sub N / L times. If the resulting string equals s, return true. If no divisor works, return false.

When to apply: Basic factor-checking approach.

Algorithm

  1. Loop L from 1 to n / 2:
  2. If n % L == 0:
  3. sub = s.substr(0, L)
  4. Construct repeated string of sub repeated n / L times.
  5. If repeated string equals s: return true.
  6. Return false.

Divisor Substring Testing Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, a, b]
Current operationSTEP 1 OF 6
Observation: Length $N = 4$
Visual state
Values and pointers at this exact step
array
S
a
b
a
b
0
↑ L=1 ("a")
1
2
3
Variables at this step
Length L
1
Sub
a
Repeats Needed
4
Check / comparison
String length N = 4. Test candidate sub-length L = 1 (4 % 1 == 0).
Decision / next transition
Candidate substring sub = s[0..0] = "a".
Why this step matters

Observation: Length N = 4. Candidate sub-lengths must divide N and satisfy L <= N/2.

Decision: Test L = 1: sub = "a".

Invariant: Repetition count k = 4 / 1 = 4.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 bool repeatedSubstringPattern(std::string s) {
7 int n = s.size();
8 for (int len = 1; len <= n / 2; ++len) {
9 if (n % len == 0) {
10 std::string sub = s.substr(0, len);
11 std::string formed = "";
12 int times = n / len;
13 for (int t = 0; t < times; ++t) {
14 formed += sub;
15 }
16 if (formed == s) return true;
17 }
18 }
19 return false;
20 }
21};
22
23int main() {
24 Solution sol;
25 std::cout << (sol.repeatedSubstringPattern("abab") ? "true" : "false") << std::endl; // true
26 std::cout << (sol.repeatedSubstringPattern("aba") ? "true" : "false") << std::endl; // false
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N * sqrt(N)) — Number of divisors of N is at most O(sqrt(N)), string construction and comparison takes O(N).
  • Space complexity: O(N)

Why Brute Force Doesn't Scale:

Linear LPS evaluation computes the exact periodic unit without looping over all divisors.

Preallocates a single contiguous integer array of size N.

2. Doubled String Search Trick

Intuition

If string s is periodic with period P, rotating s by P positions yields s itself. Concatenating s + s contains all cyclic rotations. By removing the first and last character of s + s ((s + s)[1...2N-2]), we destroy the trivial original copies at index 0 and index N. If s is still a substring of the result, s must be periodic.

When to apply: Compact and elegant formulation.

Algorithm

  1. Let doubled = s + s.
  2. Trim trimmed = doubled.substring(1, doubled.length - 1).
  3. Return trimmed.includes(s).

Doubled String Trick Search Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [b, a, b, a, b, a]
Current operationSTEP 1 OF 6
Observation: If s is periodic, circularly shifting it by one period reproduces s
Visual state
Values and pointers at this exact step
array
S
b
a
b
a
b
a
0
1
2
3
4
5
Variables at this step
Doubled Length
8
String
abababab
Check / comparison
Concatenate s with itself: doubled = s + s = "abababab".
Decision / next transition
Doubling string creates all possible circular rotations of s.
Why this step matters

Observation: If s is periodic, circularly shifting it by one period reproduces s.

Decision: Compute doubled = s + s = "abababab".

Invariant: Contains original s at index 0 and index N.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 bool repeatedSubstringPattern(std::string s) {
7 std::string doubled = s + s;
8 return doubled.substr(1, doubled.size() - 2).find(s) != std::string::npos;
9 }
10};
11
12int main() {
13 Solution sol;
14 std::cout << (sol.repeatedSubstringPattern("abab") ? "true" : "false") << std::endl; // true
15 std::cout << (sol.repeatedSubstringPattern("aba") ? "true" : "false") << std::endl; // false
16 return 0;
17}

Time & Space Complexity

  • Time complexity: O(N) — String search algorithms (Boyer-Moore / KMP inside standard libraries) run in linear time.
  • Space complexity: O(N) for doubled string

3. KMP LPS Table Periodicity (Strictly O(N))

Intuition

Compute the LPS array for string s. The final value k = lps[n - 1] is the length of the longest proper prefix that is also a suffix. The candidate repeating period length is period = n - k. If k > 0 and n % period == 0, then the prefix of length period repeated n / period times perfectly constructs s.

When to apply: The standard optimal algorithmic solution demonstrating deep mastery of string prefix automata.

Algorithm

  1. Compute lps array of size n for s.
  2. Let k = lps[n - 1].
  3. If k > 0 && n % (n - k) == 0: return true.
  4. Return false.

Divisor-Based Periodicity & Concatenation Shift Check

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, a, b]
Current operationSTEP 1 OF 6
Observation: Total length $N = 4$
Visual state
Values and pointers at this exact step
array
S
a
b
a
b
0
↑ Len 1: "a"
1
2
3
Variables at this step
Candidate Len
1
Substr
a
Repeated 4x
aaaa
Matches
false
Check / comparison
Candidate "a" repeated 4 times: "aaaa" != "abab".
Decision / next transition
Sub-length 1 fails periodicity test.
Why this step matters

Observation: Total length N = 4. Candidate sub-length L = 1 ("a").

Decision: Repeat "a" 4 times: "aaaa" !== "abab". Length 1 fails.

Invariant: Only lengths dividing N can form the string.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 bool repeatedSubstringPattern(std::string s) {
8 int n = s.size();
9 std::vector<int> lps(n, 0);
10 int len = 0, i = 1;
11
12 while (i < n) {
13 if (s[i] == s[len]) {
14 len++;
15 lps[i] = len;
16 i++;
17 } else {
18 if (len != 0) {
19 len = lps[len - 1];
20 } else {
21 lps[i] = 0;
22 i++;
23 }
24 }
25 }
26
27 int k = lps[n - 1];
28 return k > 0 && n % (n - k) == 0;
29 }
30};
31
32int main() {
33 Solution sol;
34 std::cout << (sol.repeatedSubstringPattern("abab") ? "true" : "false") << std::endl; // true
35 std::cout << (sol.repeatedSubstringPattern("aba") ? "true" : "false") << std::endl; // false
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N) strictly — LPS construction runs in exactly 2N amortized pointer increments.
  • Space complexity: O(N) for LPS table

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Divisor Length Brute ForceO(N * sqrt(N))O(N)Straightforward divisibility checking.Constructs repeating strings for each factor of N.
2.Doubled String Trick (String Rotation)O(N)O(N)One-liner code in most languages (s + s).find(s, 1) < s.size().Requires 2N string allocation.
3.KMP LPS Preprocessing (Optimal)OptimalO(N) strictlyO(N) for LPS tableDeterministic linear time, zero string duplication.Requires implementing LPS table construction.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Omitting k > 0 which falsely marks non-repeating strings as periodic.

Pitfall 2:

Assuming any string with lps[n-1] > 0 is periodic without checking n % (n - k) == 0.

Crucial Edge Cases to Validate:

  • Single character string (s = a): k = lps[0] = 0. k > 0 is false, returns false.
  • All identical characters (s = aaaa): k = 3, period = 4 - 3 = 1. 4 % 1 == 0, returns true.
  • Palindrome with no repeating period (s = aba): k = 1, period = 3 - 1 = 2. 3 % 2 != 0, returns false.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention both the doubled-string trick and KMP LPS approach.
  2. Derive why period = n - lps[n - 1] on the whiteboard.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does n % (n - lps[n - 1]) == 0 indicate that the string is periodic?

Back to DSA Sheet