Repeated Substring Pattern

How it works

If a string consists of repeated copies of a shorter block, rotating it by one block produces the same string. Doubling the string contains all such rotations. Removing the first and last positions excludes the two trivial matches, leaving a match exactly when a proper repeat exists.

Steps

1. Build s + s.
2. Remove its first and last characters.
3. Check whether s occurs in the remaining string.

Complexity

• Time: Conservative O(n²) worst-case substring search; library implementations may be faster.
• Space: O(n) for the doubled string and substring.

Things to watch for

• Exclude both trivial boundary matches.
• A one-character string cannot repeat a shorter nonempty block.
• The returned answer is a boolean, not the repeated block.

class Solution:
  def repeatedSubstringPattern(self, s: str) -> bool:
    return s in (s + s)[1:-1]

class Solution {
 public:
  bool repeatedSubstringPattern(string s) {
    const string ss = s + s;
    return ss.substr(1, ss.length() - 2).find(s) != string::npos;
  }
};