Is the given String a repeated sub-pattern?

Problem Statement

Given a string, return whether it is made of a perfectly repeated string pattern.

Evaluation

1. Correctly solve the problem (25%)


2. Run test cases (25%)


3. What is the complexity? (25%)


4. How would you optimize this? (25%)

Solution

Naiive solution

Write code to start from the zero index of the string and hypothesize an ever-growing length for the pattern. Try each starting substring for being the repetition pattern, until the length of the substring matches the length of the string. If none is found, there is no pattern.

Optimized solution

Observe that the String both starts and ends with the pattern. So by looking at the starting and ending of the String, we know both the starting and ending of the pattern.

Also observe that one can keep zig-zagging back and forth between the start- and end- based indices until the concatenation of the substrings becomes valid both in the beginning and the end of the String. In the above example:

Matching the starting and ending of the String is still not complete proof that it's the right substring. For example, in "MonkeySayDoMonkey", the pattern "Monkey" will emerge from tail optimization. But it's not the right answer and needs to be validated against the full String.

Tail optimization simply helps in doing less full-String checks in the average case, and improves depending on the length of the pattern.

References

Arthur from Google