## 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

We need to prove two things:

1, if S is not a substring in T, then S is not a periodic string:

If S is not a substring in T, then there doesn't exist a section R, where R is the prefix in the string S remove R. That means S is not a periodic string.

2, if S is a substring in T, then S is a periodic string:

If there are more than one matches of S in T, then we pick **the first match** from i to j.

We have S in T between T[i] to T[j]. That's S = T.substring(i, j).

We define the middle point as m.

We know i < m < j, because T is created by removing the first and last characters of (S + S).

Then we know

T.substring(i, m) = S.substring(0, m-i)

T.substring(m+1, j) = S.substring(m-i+1, j-i)

Here we can assume j - m > m - i (vice versa can also prove)

Then we know S.substring(0, m-i) is the prefix of S.substring(m-i+1, j-i), because T.substring(m+1, j) is from the middle point to the right, which is the start point of S.

We define string R = S.substring(0, m-i).

Because S.substring(0, m-i) is the prefix of S.substring(m-i+1, j-i), we know S.substring(m-i+1, j-i) also has prefix R. Then we know S has prefix RR, R.concat(R)

Keep doing this, we have S with the prefix of NR, which is R repeat maximum N times.

Let's define S = NR concat another String Q

Here we know Q is a suffix of S, also Q is shorter than R.

Because Q ends at the middle point m. We also know Q is a prefix of S.

Let's define R = Q concat another string W

W is the prefix of S, then W is the prefix of R, then we know (W concat Q) = R

Then we know T.substring(i - W.length, j - W.length) also matches S

Then T.substring(i, j) is not the first match of S in T. (remember we pick **the first match** S in T as i to j)

Then there is a contradiction if Q.length > 0.

So we know Q.length=0. And S = NR.

#### Implementation

This can be done efficiently by KMP algorithm in O(n) time.For a tutorial on KMP, click here KMP Algorithm.

```
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.