Code Logo

Repeated Substring Pattern

Published at25 Jul 2026
Created by
Medium 0 views
Like0

Given a string s, determine if it can be constructed by taking a substring of it and appending multiple copies of that substring together. Return true if such a pattern exists, false otherwise.

For example, "abab" can be constructed from "ab" repeated twice — return true. "abcabcabc" can be constructed from "abc" repeated three times. "aba" cannot be constructed from any repeated substring — return false. An empty or single-character string returns false.

This problem tests string pattern matching and divisor-based reasoning. The repeating substring's length must divide the total string length evenly. Once a candidate length is found, check if the substring repeats to form the full string.

The solution iterates through possible substring lengths that divide the total length. For each candidate length, take the prefix of that length and check if repeating it forms the full string.

Edge cases include an empty string (false), single character (false), a string that is exactly two repeats of a pattern (true), and a string where no divisor length works (false).

Example Input & Output

Example 1
Input
"abab"
Output
true
Explanation

"ab" repeated twice

Example 2
Input
"aba"
Output
false
Explanation

Cannot be formed by repeating a substring

Example 3
Input
"a"
Output
false
Explanation

Single char cannot be formed by repeating

Example 4
Input
""
Output
false
Explanation

Empty string

Example 5
Input
"abcabcabc"
Output
true
Explanation

"abc" repeated 3 times

Algorithm Flow

Recommendation Algorithm Flow for Repeated Substring Pattern

Solution Approach

Check each divisor length to see if repeating the prefix forms the full string.

function repeatedSubstring(s)
  n = length(s)
  for len = 1 to n / 2
    if n % len == 0
      pattern = substring(s, 0, len)
      built = ""
      for i = 1 to n / len
        built = built + pattern
      if built == s then return true
  return false

Loop through possible pattern lengths from 1 to n/2. If the length divides the total length evenly, build a string by repeating the prefix of that length. Compare the built string to the original. If they match, return true. If no length works, return false.

Time complexity is O(n^2) in the worst case, space complexity is O(n).

Best Answers

java
class Solution {
    public boolean solution(String s) {
        return s.length()>1&&(s+s).substring(1,2*s.length()-1).contains(s);
    }
}