Check Whether a String Is Built by Repetition
Company: Beaconfire
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Quick Answer: This question evaluates string manipulation and pattern recognition skills, focusing on detection of repeated substring patterns, string periodicity, and handling of boundary conditions.
Constraints
- 1 <= len(s) <= 10^4
- s contains lowercase English letters only
Examples
Input: ("abab",)
Expected Output: True
Explanation: "ab" repeated 2 times forms "abab".
Input: ("aba",)
Expected Output: False
Explanation: No non-empty proper substring can be repeated to form the full string.
Input: ("abcabcabc",)
Expected Output: True
Explanation: "abc" repeated 3 times forms "abcabcabc".
Input: ("a",)
Expected Output: False
Explanation: A single character cannot be formed by repeating a shorter non-empty proper substring.
Input: ("zzzz",)
Expected Output: True
Explanation: "z" repeated 4 times forms "zzzz".
Input: ("abcdabc",)
Expected Output: False
Explanation: Although parts of the string repeat, no proper substring repeated multiple times builds the entire string.
Hints
- If a string is built from repeating a smaller block, its prefix and suffix structure will contain useful overlap information.
- Compute the length of the longest proper prefix that is also a suffix. If this overlap is non-zero and the remaining block length divides the full length exactly, the string is repetitive.