Periodic String
Google Interview String
Find out if a given string is periodic.
e.g.
Given "abababab"
return true
Given "ababa"
return false
Given "abcdabcd"
return true
Solution
A shortcut for this problem:
Given a string S,
create a new String T by removing the first and last characters of (S + S).
If S is a substring of T, then S is periodic.
Prove
Assume S is a periodic string that consists of N repeated sections R.
(If S = "xyzxyz", then N = 2 and R = "xyz")
Known
S = N * R
T = (S + S without first and last chars), in other words the first R and last R are broken.
Hence, T = S + S - 2R = N * R + N * R - 2R = (2N - 2) * R
In order for S to be a substring of T, T has to be greater or equal to S
T >= S , replace T and S by N and R.
(2N - 2) * R >= N * R, eliminate R on both sides
2N - 2 >= N, solve the formula
N >= 2
In other words, in order for S to be a substring of T, the repetition N >= 2.
Therefore, S = N * R >= 2 * R, which implies that the pattern R repeats over twice in S.
At this point the only thing left to look at is whether S is a substring of T.
This can be done efficiently by KMP algorithm in O(n) time.
For a tutorial on KMP, click here KMP Algorithm.
Implementation
boolean isPeriodic(String s) {
StringBuilder str = new StringBuilder(s + s);
str.deleteCharAt(0);
str.deleteCharAt(str.length() - 1);
return strStr(str.toString(), s);
//click here for implementation of KMP strStr()
}
Get one-to-one training from Google Facebook engineers
Top-notch Professionals
Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.
Customized Private Class
Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.