## Interviews

#### FB Interview Question: Periodic String

Find whether string S is periodic.
Periodic indicates S = nP.
e.g.
S = "ababab", then n = 3, and P = "ab"
S = "xxxxxx", then n = 1, and P = "x"
S = "aabbaaabba", then n = 2, and P = "aabba"

Given string S, find out the P (repetitive pattern) of S.

//Solution to question O(n)
``````
boolean isPeriod(String s) {
StringBuilder str = new StringBuilder(s   s);
str.deleteCharAt(0);
str.deleteCharAt(str.length() - 1);
return strStr(str.toString(), s); //KMP strStr(T, S) to find if T has S in it.
}

//Solution to follow-up
//This method looks for the repeating pattern in string
private static String getPeriod(String string) { // O(n * n)
//for every possible period size i, check if it's valid
for (int i = 1; i <= string.length() / 2; i  ) {
if (string.length() % i == 0) {
String period = string.substring(0, i);
int j = i;
while(j + i <= string.length()) {
if (period.equals(string.substring(j, j   i))) {
j = j + i;
if(j == string.length()) { //period valid through entire string
return period;
}
} else {
break;
}
}
}

}
return null; //string is not periodic
}
``````

One-on-One Algorithm and Coding Training

One-on-One System Design Training

One-on-One Mock Interview