Determine whether a string can be formed by repeating one of its proper substrings multiple times.
Problem
Given a non-empty string s, determine whether it can be constructed by taking some substring of s and repeating it one or more times so that the final result is exactly s.
A valid repeating unit must be a proper substring of s — meaning it cannot be the whole string itself.
Return true if such a repeating pattern exists, otherwise return false.
Clarification
- The repeating substring may be any length from
1ton - 1. - The repeated copies must concatenate to form the entire string with no extra characters.
- You only need to decide whether such a pattern exists, not return the pattern itself.
Input Format
- A single string
s.
Function signature
clike
bool repeatedSubstringPattern(string s)Output Format
- Return
trueifsis composed of repeated copies of a substring. - Otherwise, return
false.
Constraints
1 <= s.length <= $10^{4}$scontains only lowercase English letters.
Example 1
Input
s = "abab"
Output
true
Explanation
The string can be formed by repeating "ab" twice: "ab" + "ab" = "abab".
Example 2
Input
s = "aba"
Output
false
Explanation
No proper substring repeated multiple times forms the entire string.
Show 1 more example
Example 3
Input
s = "abcabcabc"
Output
true
Explanation
The substring "abc" repeated 3 times gives the original string.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.