You are given a string s.
Your task:

Determine whether s can be constructed by repeating a substring multiple times.

Examples:

Input:  "abab"
Output: true
Explanation: "ab" repeated twice forms "abab"

Input: "aba"
Output: false

Input: "abcabcabc"
Output: true

Input: "a"
Output: false

---

Problem Understanding

We need to check:

Does there exist a substring t such that:

t repeated k times = s
where k ≥ 2

Observations:

• The repeated pattern must divide the string length evenly.
• The substring must tile the entire string without mismatches.
• Brute forcing all substrings works logically but is inefficient.

Better insight exists.

---

Logic Explained in Simple English

Here’s the cleanest way to think about it:

Key idea:

If a string is made from repeating a substring, then:

Take s, double it: s + s
Remove the first and last character
If s appears inside this new string, then s is a repeated pattern

Why this works:

• Doubling creates overlapping repetition regions
• Removing ends avoids trivial self-inclusion
• If s fits inside, it means it can be rotated to match itself
• Rotation symmetry occurs only if string repeats

Example with “abab”:

s = "abab"
s+s = "abababab"
trim ends → "bababa"
"abab" appears inside → true

Example with “aba”:

s = "aba"
s+s = "abaaba"
trim ends → "baab"
"aba" does NOT appear → false

This gives a very fast and elegant solution.

---

Alternative Logic (Divisor Check)

Another way:

1. Let n = length of s
2. For each divisor d of n (excluding n itself):
   • Check if repeating s[0:d] (n/d times) equals s
3. If any works → true
4. Else → false

This works but is slower and more code-heavy.

---

Step-by-Step Approach (Using String Trick)

1. Let doubled = s + s
2. Remove first and last character
3. If s is a substring of the result → return true
4. Otherwise return false

---

Java Implementation

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String doubled = s + s;
        String trimmed = doubled.substring(1, doubled.length() - 1);
        return trimmed.contains(s);
    }
}

---

Dry Run Example

Input:

s = "abcabcabc"

Step 1:

doubled = "abcabcabcabcabcabc"

Step 2:

trimmed = "bcabcabcabcabcabca"

Step 3:
Check if trimmed contains s:

"bcabcabcabcabcabca".contains("abcabcabc") → true

Return:

true

Another dry run:

Input:

s = "abcd"

doubled:

"abcdabcd"

trimmed:

"bcdabc"

Contains?

false

Return:

false

---

Time and Space Complexity

Time Complexity

O(n)

String concatenation + contains search runs efficiently.

Space Complexity

O(n)

Due to doubled string.

---

Common Mistakes and How to Avoid Them

1. Thinking substring length must be ≤ n/2
   Correct, but manually checking is unnecessary with string trick.
2. Checking only first half of string
   Must check all divisors, not just half.
3. Using nested loops to compare characters
   Leads to O(n²) or worse.
4. Returning true for single-character string
   Must require at least two repeats, so return false for length 1.
5. Forgetting that contains must check whole s, not partial match
   Only full match matters.