DSA problem
Repeated Substring Pattern
Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. Return true if it can; otherwise return false. The substring must be a proper substring (strictly shorter than s itself).
A short, elegant trick solves this in one line. Form the string (s + s) and remove the first and last characters, producing a string of length 2n - 2. The string s is built from repetitions of one of its proper substrings if and only if s appears inside this trimmed doubled string. The intuition is that doubling s lines up every cyclic rotation of s as a substring; the trim discards the trivial rotation by zero and the trivial rotation by n, leaving only the genuine cyclic shifts. If s itself is among them, it must be periodic.
A more algorithmic answer uses the KMP failure (LPS) array. Build the LPS array for s; let p = lps[n - 1], the length of the longest proper prefix that is also a suffix. The string is composed of repetitions of a smaller block if and only if p > 0 and n - p divides n. The repeated unit has length exactly n - p.
Both approaches run in O(n) time. The slice-and-search trick is the cleanest one-liner; the KMP version is more illuminating because it explicitly identifies the repeating period of the string.
Examples
s = "abab"trues = "aba"falses = "abcabcabcabc"trueConstraints
- 1 <= s.length <= 10^4
- s consists of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.