Smallest Repeating Unit
Problem
Given a non-empty string s, return the shortest string u such that s is u written a whole number of times in a row. If no shorter unit works, the answer is s itself. The answer should take O(n) time.
Examples
Input: s = "xyzxyzxyz"
Output: "xyz"
Why: three copies of "xyz"Input: s = "abaab"
Output: "abaab"
Why: a shift of 3 lines "ab" up with itself, but 3 does not divide 5Input: s = "q"
Output: "q"
Why: edge case, a single letter is its own unitHints
0 / 3
If s is made of copies of u, then shifting s by the length of u lines it up with itself. That is a statement about a prefix of s that is also a suffix.
The longest proper prefix that is also a suffix is the last value of the failure table used for string matching. Its length tells you the smallest shift that lines s up with itself.
Build the failure table, let b be its last value and p be n - b. If p divides n, the prefix of length p is the answer; otherwise no shorter unit exists and the answer is s.
Solution
A string is its first p characters repeated exactly when p divides n and s lines up with itself after a shift of p, and the shifts that line up correspond to borders, prefixes that are also suffixes. The longest border b gives the smallest such shift, p = n - b. When p divides n that prefix is the unit; when it does not, the periodicity lemma rules out every longer shift that divides n as well, so s is its own unit. The failure table takes linear time thanks to the fall-back to shorter borders on a mismatch. Time is O(n) and space is O(n).
def smallest_unit(s):
border = [0] * len(s)
for i in range(1, len(s)):
k = border[i - 1]
while k and s[i] != s[k]:
k = border[k - 1] # fall back to a shorter border
if s[i] == s[k]:
k += 1
border[i] = k
p = len(s) - border[-1] # the smallest shift that lines s up with itself
return s[:p] if len(s) % p == 0 else s
print(smallest_unit("xyzxyzxyz")) # -> xyz
print(smallest_unit("abaab")) # -> abaab
print(smallest_unit("q")) # -> qStuck on the idea rather than the code? String Matching Intuition covers it.