Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Repeated Substring Pattern

Problem (restated)

Return whether s is a concatenation of two or more copies of a shorter string.

Intuition

If s is t repeated k ≥ 2 times, the LPS of s ends at n - |t|. The period is n - lps[n-1]; it tiles s iff that period divides n and is strictly smaller than n.

Approaches

LPS period check

Unverified

Time O(n)Space O(n)

Idea. Build LPS. Let p = lps[n-1]. Return p > 0 && n % (n - p) == 0.

Walkthrough. abab → lps last 2, period 2, 4 % 2 == 0 → true. aba → last 1, period 2, 3 % 2 ≠ 0 → false.

Trade-offs. The one-liner s in (s+s)[1:-1] is a cute equivalent. LPS is the KMP explanation.

Solution

export function repeatedSubstringPattern(s: string): boolean {
  const n = s.length;
  if (n < 2) return false;
  const lps = new Array<number>(n).fill(0);
  let length = 0;
  for (let i = 1; i < n; i++) {
    while (length > 0 && s[i] !== s[length]) length = lps[length - 1]!;
    if (s[i] === s[length]) length++;
    lps[i] = length;
  }
  const p = lps[n - 1]!;
  return p > 0 && n % (n - p) === 0;
}

export function repeatedSubstringPattern(s: string): boolean {
  const n = s.length;
  if (n < 2) return false;
  const lps = new Array<number>(n).fill(0);
  let length = 0;
  for (let i = 1; i < n; i++) {
    while (length > 0 && s[i] !== s[length]) length = lps[length - 1]!;
    if (s[i] === s[length]) length++;
    lps[i] = length;
  }
  const p = lps[n - 1]!;
  return p > 0 && n % (n - p) === 0;
}

Template connection

Period from LPS, same array as LC 28 / LC 1392.

Reflection

Let p be the last LPS value. The string repeats when p > 0 and n % (n - p) == 0. The period is n - p.
One character is false. aba has LPS 1, and 3 is not divisible by 2.
abcabc has LPS 3, period 3, so it is true. A proper suffix is not the whole string.