459. Repeated Substring Pattern

How to solve Repeated Substring Pattern (LeetCode 459): the approach in brief

The problem

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

Pattern

Repeated Substring Pattern is a String Manipulation Patterns problem, in the Repeated Substring Pattern Detection subpattern. The pattern covers palindrome checking, anagram detection, pattern matching, and string conversion

Learn to detect if a string can be constructed by repeating a substring pattern.

Approach outline

1. Think about how you can use string properties to determine if the entire string is made by repeating a smaller substring.
2. Consider the lengths of possible substrings that could repeat to form the original string; what constraints do these lengths have relative to the full string length?
3. Try checking substrings of the original string that are prefixes and see if repeating them enough times reconstructs the original string.

Complexity

The reference solution runs in O(n) time and O(n) space.

Asked at

Repeated Substring Pattern has been reported in interviews at Google.