The problem. Given a string s, return true if it can be built by writing one substring two or more times in a row, like "abcabcabc" from "abc".
s = "abab" -> true ("ab" twice)
s = "aba" -> false
s = "abcabcabcabc" -> true ("abc" four times, or "abcabc" twice)
s = "abacaba" -> false (starts and ends with "aba", but 7 letters don't split into blocks)If s is a block B written k ≥ 2 times, then dropping the first block or the last block leaves the same string. So s has a border — a prefix that is also a suffix — of length n - |B|, and shifting s by |B| places lines it up with itself. That gives two quick tests: look for s inside a doubled copy of itself, or read the longest border from the KMP table.
A border alone isn't enough. "abacaba" has the border "aba", so shifting by 4 lines it up — but 4 doesn't divide 7, and the last block would be cut short. The shift has to split the string into whole blocks.
A block length must divide n. Try each one up to n / 2, and check whether repeating the first block rebuilds s.
function repeatedSubstringPattern(s) { const n = s.length; for (let len = 1; len <= n / 2; len++) { if (n % len !== 0) continue; // blocks must fit exactly if (s.slice(0, len).repeat(n / len) === s) return true; } return false;}Time O(n · d), space O(n), where d is the number of divisors of n — each check costs O(n). d is small in practice (at most 2√n), so this is fast enough for most inputs.
Write s twice and cut off the first and last letter. If s is a repeated block, it still appears inside — starting one block in. If it isn't, the only copies of s in s + s are at the very start and the very end, and both have been cut.
function repeatedSubstringPattern(s) { return (s + s).slice(1, -1).includes(s); // s must appear somewhere in the middle}Time O(n) with a linear search such as KMP, space O(n) for the doubled string. The built-in search is usually fast, but some libraries fall back to O(n²) on unlucky inputs — so say which search you're assuming.
Build the KMP table for s; the last entry is the longest border, and n minus it is the block length.
function repeatedSubstringPattern(s) { const n = s.length; const lps = new Array(n).fill(0); for (let i = 1, len = 0; i < n; ) { if (s[i] === s[len]) lps[i++] = ++len; else if (len > 0) len = lps[len - 1]; else lps[i++] = 0; } const border = lps[n - 1]; // the longest prefix that is also a suffix const period = n - border; // s shifted by period lines up with itself return border > 0 && n % period === 0; // the shift must cut s into whole blocks}Time O(n), space O(n). Why is the longest border the right one to check? It gives the smallest shift, and if any block length works, the smallest shift divides it — so testing that one shift is enough.
The doubling trick is linear only with a linear-time search such as KMP. It is the one-liner interviewers like to see explained; the KMP version shows why it runs in linear time.
"a" is false: a block must appear at least twice."aaaa" is true."abacaba" and "aabaaba" are false; forgetting the n % period check says true."abababab" works with "ab" and "abab"; any one is enough.a are needed so that b is a substring: repeat until long enough, then one search.goal a rotation of s? The same doubling trick: (s + s).includes(goal) with equal lengths.lps[n - 1].