## Google Interview Question for Software Engineers

• 5

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 2 vote

KMP prefix table algorithm can help

Comment hidden because of low score. Click to expand.
0
of 4 vote

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

Comment hidden because of low score. Click to expand.
-1

This method will return null every time.

Comment hidden because of low score. Click to expand.
-2

yep this code doesn't work

Comment hidden because of low score. Click to expand.
-1
of 1 vote

yep this code is wrong

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````O(N^3) solution

Boolean isPeriodic(String str) {
if (isSameCharacters(str)) {
return true;
}

int maxLength =. str.length() / 2
while (maxLength >= 1) {
if (isMatch(maxLength, str.length() - maxLength, str.length(),str)) {
boolean middleSegment = isMatch(maxLength, maxLength, str.length() - maxLength,str)
if (middleSegment) {
return true;
}
}
maxLength -= 1;
}
return false;
}

Boolean isMatch( int patternEnd, int start, int end, String str) {
if (start > end) {
return true;
}
int lenRegion = end - start;
if (patternEnd % lenRegion != 0) {
return false;
}

for (int i = start; i+ patternEnd < end; i += patternEnd) {
for (int j = 0; j < patternEnd; j++) {
if (str.charAt(j) != str.charAt(I + j)) {
return false;

}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public String findRepPattern(String str) {
int len = str.length();
for(int i = 1; i <= len/2; ++i) {
if (len % i == 0) {
String prefix = str.substring(0, i);
int start = i;
boolean found = true;

while (start < len && found) {
String lastPrefix = str.substring(start, start + i);
if (lastPrefix.equals(prefix)) {
start += i;
} else {
found = false;
}
}

if (start == len) {
System.out.println("pattern: " + prefix + " N = " + (len / prefix.length()));
return prefix;
}
}
}
return null;
}``````

Comment hidden because of low score. Click to expand.
0

i think if its a periodic string then it has to be of even length,
then if (len % 2 == 0) can be validated and avoid unnecessary processing inside the loop.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
using namespace std;

string GetPeriodicString(string s)
{
int length = s.length();
int* lps = new int[length];
lps[0] = 0;
for(int i=1; i<length; i++)
{
int len = lps[i-1];
while(len > 0)
{
if(s[i] == s[len])
{
lps[i] = len + 1;
break;
}
else
{
len = lps[len-1];
}
}
if(len == 0)
{
if(s[i] == s[0])
{
lps[i] = 1;
}
else
{
lps[i] = 0;
}
}
}
int x = length - lps[length-1];
for(int i=length-x-1; i>=x; i-=x)
{
if(i+1-lps[i] != x)
{
return s;
}
}
return s.substr(0, x);
}
int main() {
string s;
cin>>s;
cout<<GetPeriodicString(s);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

s = input()
l = len(s)
st = ""
b = 0
for i in range (l):
st+=s[i]
b1 = 1
for j in range(i+1, l, i+1):
if(s[j: j+i+1]!=st):
b1=0
break
if(b1==1):
b=1
break
if(b==1):
print(st)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````s = input()
l = len(s)
st = ""
b = 0
for i in range (l):
st+=s[i]
b1 = 1
for j in range(i+1, l, i+1):
if(s[j: j+i+1]!=st):
b1=0
break
if(b1==1):
b=1
break
if(b==1):
print(st)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````s=str(input())
n=len(s)
for i in range(1,n+1):
if n%i==0:
x=s[:i]
if x*(n//i) == s:
print(x, n//i)
break``````

Comment hidden because of low score. Click to expand.
0

the for loop just need to go from 1 to n and not n+1

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static boolean isPeriodic(String S) {
int n = S.length();
for(int i=1 ; i < n ; ++i ) {
String p = S.substring(0, i);
String[] parts = S.split(p);
if( parts.length == 0 ) {
System.out.println(p);
return true;
}
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0

Loop just need to go until (n/2) + 1

Comment hidden because of low score. Click to expand.
0

The loop needs to go only until (n/2)+1

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class GNPString {

public static boolean verify(int n, String pattern, String input)
{
int m = 0;
for(int i = 0; i < input.length(); i += pattern.length())
{
if(input.substring(i, i + pattern.length()).compareTo(pattern) == 0)
{
++m;
}
else
{
return false;
}
}

return m == (input.length()/n);
}

public static int GetN(char[] input)
{
int j = input.length-1;
int k = input.length-1;
char[] pattern = new char[input.length];
int len = 0;

String in = new String(input);

while(j > 0)
{
++len;

if(verify(len, new String(input, j, len), in))
{
return (input.length/len);
}

--j;
}

return 0;
}

public static void main(String[] args)
{
System.out.println(GetN(new String("abababab").toCharArray()));

System.out.println(GetN(new String("aabaab").toCharArray()));

System.out.println(GetN(new String("aaaa").toCharArray()));

System.out.println(GetN(new String("aabaaaba").toCharArray()));

System.out.println(GetN(new String("axbayb").toCharArray()));
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class GNPString {

public static boolean verify(int n, String pattern, String input)
{
int m = 0;
for(int i = 0; i < input.length(); i += pattern.length())
{
if(input.substring(i, i + pattern.length()).compareTo(pattern) == 0)
{
++m;
}
else
{
return false;
}
}

return m == (input.length()/n);
}

public static int GetN(char[] input)
{
int j = input.length-1;
int k = input.length-1;
char[] pattern = new char[input.length];
int len = 0;

String in = new String(input);

while(j > 0)
{
++len;

if(verify(len, new String(input, j, len), in))
{
return (input.length/len);
}

--j;
}

return 0;
}

public static void main(String[] args)
{
System.out.println(GetN(new String("abababab").toCharArray()));

System.out.println(GetN(new String("aabaab").toCharArray()));

System.out.println(GetN(new String("aaaa").toCharArray()));

System.out.println(GetN(new String("aabaaaba").toCharArray()));

System.out.println(GetN(new String("axbayb").toCharArray()));
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def string_period(msg):
for k in range(1, len(msg)):
if msg == (msg[k:] + msg[:k]):
break
return msg[:k]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public boolean repeatedSubstringPattern(String s) {
int prefixTable[] = new int[s.length()];
int i = 0;
int j = 1;
while (j < s.length()) {
if (s.charAt(i) == s.charAt(j))
prefixTable[j++] = ++i;
else if (i > 0)
i = prefixTable[i - 1];
else
j++;
}
return prefixTable[s.length() - 1] > 0 && s.length() % (s.length() - prefixTable[s.length() - 1]) == 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````function findPeriod(s) {
for (var i = 1; i <= s.length / 2; ++i) {
if (s.length % i === 0) {
const n = s.length / i;
const c = s.substring(0, i);
if (c.repeat(n) === s) return [n, c];
}
}

return null;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* A class for checking periodicity of a string.
*/
public class PeriodicString {
/**
* Recursively check for periodic.
* @param rest Rest of the string to be checked.
* @param current The substring for which we are checking periodicity.
* @param ocr Number of occurrence.
* @return true when periodic or check for the rest string.
*/
private static boolean isPeriodicStringWith(String rest, String current, int ocr) {
if (ocr > 1 && rest.isEmpty()) {
return true;
}
if (!rest.startsWith(current)) {
return false;
}
return isPeriodicStringWith(rest.substring(current.length()), current, ocr + 1);
}

/**
* Checking if a string is periodic.
* @param input The input string.
* @return true when the whole string is periodic.
*/
public static boolean isPeriodic(String input) {
if (input != null) {
for (int i = 1; i <= input.length() / 2; i++) {
if (isPeriodicStringWith(input.substring(i), input.substring(0, i), 1)) {
return true;
}
}
}
return false;
}

/**
* Run sample test cases.
* @param args command line arguments. Not required.
*/
public static void main(String[] args) {
System.out.println(isPeriodic("xxxxx"));
System.out.println(isPeriodic("ababababab"));
System.out.println(isPeriodic("ababaababa"));
System.out.println(isPeriodic("ababaabab"));
System.out.println(isPeriodic("a"));
System.out.println(isPeriodic(""));
System.out.println(isPeriodic(null));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def checkPattern(selection, mainstring):
lengthOfPattern=len(selection)
n = 0
for i in range(len(mainstring)):
if mainstring[i] == selection[i%len(selection)]:
lengthOfPattern-=1
else:
return -1
if lengthOfPattern == 0:
lengthOfPattern=len(selection)
n+=1
if lengthOfPattern != len(selection) or n == 0:
return -1
return n

def findPattern(mainstring):
selection=''
for i in range(len(mainstring)):
selection+=mainstring[i]
n = checkPattern(selection,mainstring[i+1:])
if n != -1:
break
if n == -1:
print 'No pattern'
else:
print 'n =',n,'Pattern=',selection
return

findPattern('xdxdxdxd')``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def checkPattern(selection, mainstring):
lengthOfPattern=len(selection)
n = 0
for i in range(len(mainstring)):
if mainstring[i] == selection[i%len(selection)]:
lengthOfPattern-=1
else:
return -1
if lengthOfPattern == 0:
lengthOfPattern=len(selection)
n+=1
if lengthOfPattern != len(selection) or n == 0:
return -1
return n

def findPattern(mainstring):
selection=''
for i in range(len(mainstring)):
selection+=mainstring[i]
n = checkPattern(selection,mainstring[i+1:])
if n != -1:
break
if n == -1:
print 'No pattern'
else:
print 'n =',n,'Pattern=',selection
return

findPattern('xdxdxdxd')``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

def checkPattern(selection, mainstring):
lengthOfPattern=len(selection)
n = 0
for i in range(len(mainstring)):
if mainstring[i] == selection[i%len(selection)]:
lengthOfPattern-=1
else:
return -1
if lengthOfPattern == 0:
lengthOfPattern=len(selection)
n+=1
if lengthOfPattern != len(selection) or n == 0:
return -1
return n

def findPattern(mainstring):
selection=''
for i in range(len(mainstring)):
selection+=mainstring[i]
n = checkPattern(selection,mainstring[i+1:])
if n != -1:
break
if n == -1:
print 'No pattern'
else:
print 'n =',n+1,'Pattern=',selection
return

if __name__ == "__main__":
test_cases = [
'aaaaaaa',
'bbb',
'ab'*50,
'asd'*20
]

for each in test_cases:
findPattern(each)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def checkPattern(selection, mainstring):
lengthOfPattern=len(selection)
n = 0
for i in range(len(mainstring)):
if mainstring[i] == selection[i%len(selection)]:
lengthOfPattern-=1
else:
return -1
if lengthOfPattern == 0:
lengthOfPattern=len(selection)
n+=1
if lengthOfPattern != len(selection) or n == 0:
return -1
return n

def findPattern(mainstring):
selection=''
for i in range(len(mainstring)):
selection+=mainstring[i]
n = checkPattern(selection,mainstring[i+1:])
if n != -1:
break
if n == -1:
print 'No pattern'
else:
print 'n =',n+1,'Pattern=',selection
return

if __name__ == "__main__":
test_cases = [
'aaaaaaa',
'bbb',
'ab'*50,
'asd'*20
]

for each in test_cases:
findPattern(each)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is how I'd do it, inspiration leetcode 459

``````private static String FindPattern(String input) throws NoSuchObjectException {
int repeatPos=(input+input).indexOf(input,1);
if (repeatPos==-1)
else
return input.substring(0,repeatPos);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def isPeriodic(input):
if not input or input is None:
return None

return helper(0, input)

def helper(idx, substring):
char = substring[:idx]
if len(substring.replace(char, '')) == 0:
return (char, substring.count(char))

return helper(idx + 1, substring)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````var input = "abababab";

var isPeriodic = false;

var midPoint = Math.ceil(input.length / 2);

// We split the string in half... the max length of a pattern cannot be more
// than half the length of the string
var left = input.substring(0, midPoint);

for (var i = left.length; i > 0; i--) {
var newPattern = left.substring(0, i);
// Want to check if repeating newPattern results in the input string
var j = 1;
do {
var someString = newPattern.repeat(j);
if (someString === input) {
isPeriodic = true;
console.log("String is periodic: n = " + j + ", P = " + newPattern);
break;
} else j++;
} while (someString.length <= input.length);
}

if (!isPeriodic) {
console.log("Not a periodic string.")``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````var input = "abababab";

var isPeriodic = false;

var midPoint = Math.ceil(input.length / 2);

// We split the string in half... the max length of a pattern cannot be more
// than half the length of the string
var left = input.substring(0, midPoint);

for (var i = left.length; i > 0; i--) {
var newPattern = left.substring(0, i);
// Want to check if repeating newPattern results in the input string
var j = 1;
do {
var someString = newPattern.repeat(j);
if (someString === input) {
isPeriodic = true;
console.log("String is periodic: n = " + j + ", P = " + newPattern);
break;
} else j++;
} while (someString.length <= input.length);
}

if (!isPeriodic) {
console.log("Not a periodic string.")
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

var input = "abababab";

var isPeriodic = false;

var midPoint = Math.ceil(input.length / 2);

// We split the string in half... the max length of a pattern cannot be more
// than half the length of the string
var left = input.substring(0, midPoint);

for (var i = left.length; i > 0; i--) {
var newPattern = left.substring(0, i);
// Want to check if repeating newPattern results in the input string
var j = 1;
do {
var someString = newPattern.repeat(j);
if (someString === input) {
isPeriodic = true;
console.log("String is periodic: n = " + j + ", P = " + newPattern);
break;
} else j++;
} while (someString.length <= input.length);
}

if (!isPeriodic) {
console.log("Not a periodic string.")
}

Comment hidden because of low score. Click to expand.
0
of 0 vote
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{public String findSubstring(String str)
{
if(str==null || str.length()==1)
return null;
//aaabcaaabc
int p1=0;
int p2=1;
while(p2<=str.length()/2){

while(str.charAt(p2)!=str.charAt(p1))
{
if(p2 >str.length()/2)
return null;
p2++;
if(p2>str.length()/2)return null;
}
boolean check = findSubstringHelper(str.substring(p1, p2),str.substring(p2));
if(check) return str.substring(p1, p2);
p2++;
}

return null;
}

public boolean findSubstringHelper(String substr,String str)
{
int start=0;
int end=substr.length();
while( end<=str.length())
{
if(!str.substring(start, end).equalsIgnoreCase(substr)) return false;
start=end;
end=start+substr.length();

}
if(start<str.length() && end>str.length()) return false;
return true;
}}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public String findSubstring(String str)
{
if(str==null || str.length()==1)
return null;
//aaabcaaabc
int p1=0;
int p2=1;
while(p2<=str.length()/2){

while(str.charAt(p2)!=str.charAt(p1))
{
if(p2 >str.length()/2)
return null;
p2++;
if(p2>str.length()/2)return null;
}
boolean check = findSubstringHelper(str.substring(p1, p2),str.substring(p2));
if(check) return str.substring(p1, p2);
p2++;
}

return null;
}

public boolean findSubstringHelper(String substr,String str)
{
int start=0;
int end=substr.length();
while( end<=str.length())
{
if(!str.substring(start, end).equalsIgnoreCase(substr)) return false;
start=end;
end=start+substr.length();

}
if(start<str.length() && end>str.length()) return false;
return true;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

def nPattern(String):
if(len(String)==0):
return "",0
pattern = ""
patternCounter = 1
patternCheckStart = 0
patternEndCheck = 0
for i in range(0,len(String)):
if(patternCheckStart==len(String)):
break
if(pattern == ""):
pattern = String[i]
if(len(String)%len(pattern)==0):
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

while(patternCheckStart < len(String)):
if(pattern==String[patternCheckStart:patternEndCheck]):
patternCheckStart = patternEndCheck
patternEndCheck = patternCheckStart+len(pattern)
patternCounter = patternCounter+1
else:
pattern = String[0:patternCheckStart+1]
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

return pattern,patternCounter

Comment hidden because of low score. Click to expand.
0
of 0 vote

def nPattern(String):
pattern = ""
patternCounter = 1
patternCheckStart = 0
patternEndCheck = 0
for i in range(0,len(String)):
if(patternCheckStart==len(String)):
break
if(pattern == ""):
pattern = String[i]
if(len(String)%len(pattern)==0):
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

while(patternCheckStart < len(String)):
if(pattern==String[patternCheckStart:patternEndCheck]):
patternCheckStart = patternEndCheck
patternEndCheck = patternCheckStart+len(pattern)
patternCounter = patternCounter+1
else:
pattern = String[0:patternCheckStart+1]
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

return pattern,patternCounter

print(nPattern("bdsxmgh"))

Comment hidden because of low score. Click to expand.
0
of 0 vote

def nPattern(String):
pattern = ""
patternCounter = 1
patternCheckStart = 0
patternEndCheck = 0
for i in range(0,len(String)):
if(patternCheckStart==len(String)):
break
if(pattern == ""):
pattern = String[i]
if(len(String)%len(pattern)==0):
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

while(patternCheckStart < len(String)):
if(pattern==String[patternCheckStart:patternEndCheck]):
patternCheckStart = patternEndCheck
patternEndCheck = patternCheckStart+len(pattern)
patternCounter = patternCounter+1
else:
pattern = String[0:patternCheckStart+1]
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

return pattern,patternCounter

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
def nPattern(String):
pattern = ""
patternCounter = 1
patternCheckStart = 0
patternEndCheck = 0
for i in range(0,len(String)):
if(patternCheckStart==len(String)):
break
if(pattern == ""):
pattern = String[i]
if(len(String)%len(pattern)==0):
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

while(patternCheckStart < len(String)):
if(pattern==String[patternCheckStart:patternEndCheck]):
patternCheckStart = patternEndCheck
patternEndCheck = patternCheckStart+len(pattern)
patternCounter = patternCounter+1
else:
pattern = String[0:patternCheckStart+1]
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

return pattern,patternCounter
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package com.company;

import java.lang.Math;

public class Main {

//this can be done in O(n^(3/2)) complexity.
static String isPeriodic(String S){

int len_of_s = S.length();
int len_of_p = len_of_s + 1;
int sq_len = (int)Math.sqrt(len_of_s);
// this loop is run √ length(s) time and in each iteration isPossible is called whose complexity is O(length(S))
// hence overall complexity is length(S)^(3/2)
for(int i = 1; i < sq_len; i++){
if(len_of_s%i == 0){
int x = i;
int y = len_of_s/i;
if(isPossible(S,x)){
len_of_p = Math.min(len_of_p,x);
}
else if(isPossible(S,y)){
len_of_p = Math.min(len_of_p,y);
}
}
}
String res = "Not periodic";
if(len_of_p != len_of_s+1){
res = S.substring(0,len_of_p);
}
return res;
}
static boolean isPossible(String S, int len_of_expected_p){
String p = S.substring(0,len_of_expected_p);
for(int i = 0; i < S.length(); i += len_of_expected_p){
if(!p.equals(S.substring(i,i+len_of_expected_p))){
return false;
}
}
return true;
}

public static void main(String[] args) {
/*
* 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.
* */
System.out.println(isPeriodic("aabbaaabba"));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def is_periodic(input_string, is_return_first=True):
input_length = len(input_string)
result = (False, 0, '')
pattern_length = 1
while pattern_length <= int(input_length / 2):
if input_length % pattern_length == 0:
is_pattern_equal = True
pattern_string = input_string[:pattern_length]
pattern_multiplier = int(input_length / pattern_length)
j = 0
while (j < pattern_length) and is_pattern_equal:
for k in range(1, pattern_multiplier):
if input_string[j] != input_string[k * pattern_length + j]:
is_pattern_equal = False
break
j += 1
if is_pattern_equal:
result = (True, pattern_multiplier, pattern_string)
if is_return_first:
return result
pattern_length += 1
return result

print(is_periodic('abababababababababababab'))
print(is_periodic('xxxxxx', False))
print(is_periodic('aabbaaabba'))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
int i,j,k=0;
string s,d,c;
cin>>s;
int count[s.length()];
for (i=0; i<s.length(); i++)
{
count[i]=1;
k++;
d=s.substr(0,i+1);
for (j=i+1; j<s.length(); j+=k)
{
c=s.substr(j,k);
if (d==c)
{
count[i]++;
continue;
}
break;
}
}
//cout<<count<<endl;
sort(count,count+s.length());
for (i=s.length()-1; i>=0; i--)
{
if (count[i]>1 && s.length()%count[i]==0)
{
cout<<"periodic"<<" "<<(s.length()/count[i]) <<endl;
return 0;
}
else if (count[i]==1)
{
cout << "not periodic" << endl;
return 0;
}
}
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
int i,j,k=0;
string s,d,c;
cin>>s;
int count[s.length()];
for (i=0; i<s.length(); i++)
{
count[i]=1;
k++;
d=s.substr(0,i+1);
for (j=i+1; j<s.length(); j+=k)
{
c=s.substr(j,k);
if (d==c)
{
count[i]++;
continue;
}
break;
}
}
//cout<<count<<endl;
sort(count,count+s.length());
for (i=s.length()-1; i>=0; i--)
{
if (count[i]>1 && s.length()%count[i]==0)
{
cout<<"periodic"<<"    "<<(s.length()/count[i]) <<endl;
return 0;
}
else if (count[i]==1)
{
cout << "not periodic" << endl;
return 0;
}
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the most important thing is to get the set of lengths.
The available length is a prime of string length and all length are combination of the primes.
If you find a prime up to square root of the string length, you can find another prime.
Then, the time complexity to get the set of lengths is O(square root of N), N is the string length.
The maximum number of the set of length is 2 X square root of N.

Therefore, the total time complexity is O(square root of N)

``````bool isPeriodic(const string& str, int len)
{
for (int i = len, last = str.size() - len -1; i < last; i += len)
{
for (int k = 0; k < len; k++) {
if (str[k] != str[i + k])
return false;
}
}
return true;
}

string findPeriodic(const string& str)
{
int size = str.size();
list<int> lengths = { 1 };
for (int len = 2, max_len = sqrt(size); len <= max_len; len++)
{
if (size % len == 0) {
lengths.push_back(len);
lengths.push_back(size/len);
}
}

for (int len : lengths)
{
if (isPeriodic(str, len))
return str.substr(0, len);
}
return str;
}

int main()
{
string s[] = { "ababab", "xxxxxx", "aabbaaabba" };
for (int i = 0; i < _countof(s); i++)
cout << findPeriodic(s[i]) << endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;

string find(string str)
{
int i=0,j=1,l=1;
int len=str.length();
for(int k=1;k<len;k++)
{
if(str.at(k)==str.at(i))
{
i++;
}
else
{
k=l;
l++;
i=0;
// cout<<l<<endl;

}
if(l==i)
{
i=0;
}

}
if(len%l!=0) l=len;
return str.substr(0,l);
}

int main()
{
string str="abaababa";
cout<<find(str);

return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;

string find(string str)
{
int i=0,j=1,l=1;
int len=str.length();
for(int k=1;k<len;k++)
{
if(str.at(k)==str.at(i))
{
i++;
}
else
{
k=l;
l++;
i=0;
// cout<<l<<endl;

}
if(l==i)
{
i=0;
}

}
if(len%l!=0) l=len;
return str.substr(0,l);
}

int main()
{
string str="abaababa";
cout<<find(str);

return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;

string find(string str)
{
int i=0,j=1,l=1;
int len=str.length();
for(int k=1;k<len;k++)
{
if(str.at(k)==str.at(i))
{
i++;
}
else
{
k=l;
l++;
i=0;
// cout<<l<<endl;

}
if(l==i)
{
i=0;
}

}
if(len%l!=0) l=len;
return str.substr(0,l);
}

int main()
{
string str="abaababa";
cout<<find(str);

return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Solution {
public:
int solve(string s) {

string tmps = s + s;

int n = 0;
int i = 0;
string pattern;
while (i < s.length()) {
int d = tmps.find(s, i+1);
if (d < s.length() && pattern.empty())
pattern = tmps.substr(i, d-i);
i = d;
n++;
}
cout<<"pattern=["<<pattern<<"]["<<n<<"]"<<endl;
return pattern;
}
};

int main(int argc, char* argv[]) {
Solution s;

s.solve("ababab");

cout<<"-------------------------"<<endl;
s.solve("xxxxxx");
cout<<"-------------------------"<<endl;
s.solve("aabbaaabba");
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Solution {
public:
int solve(string s) {

string tmps = s + s;

int n = 0;
int i = 0;
string pattern;
while (i < s.length()) {
int d = tmps.find(s, i+1);
if (d < s.length() && pattern.empty())
pattern = tmps.substr(i, d-i);
i = d;
n++;
}
cout<<"pattern=["<<pattern<<"]["<<n<<"]"<<endl;
return pattern;
}
};

int main(int argc, char* argv[]) {
Solution s;

s.solve("ababab");

cout<<"-------------------------"<<endl;
s.solve("xxxxxx");
cout<<"-------------------------"<<endl;
s.solve("aabbaaabba");
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
public static void main(String[] args) {

String s = "aabbaaaabba";
String tString =new String();
int i=0;
String finalString=null;
while(i<s.length()/2) {
char c = s.charAt(i);
tString = tString+new StringBuilder(c+"").toString();
if(s.lastIndexOf(tString)!=i) {
finalString = tString;
}
i++;
}
System.out.println(finalString);
String s1= s.replaceAll(finalString, "");
if(s1.equals("")) {
System.out.println(s.length()/finalString.length());
}else {
System.out.println((s.length()-s1.length())/finalString.length());
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void main(String[] args) {

String s = "aabbaaaabba";
String tString =new String();
int i=0;
String finalString=null;
while(i<s.length()/2) {
char c = s.charAt(i);
tString = tString+new StringBuilder(c+"").toString();
if(s.lastIndexOf(tString)!=i) {
finalString = tString;
}
i++;
}
System.out.println(finalString);
String s1=	s.replaceAll(finalString, "");
if(s1.equals("")) {
System.out.println(s.length()/finalString.length());
}else {
System.out.println((s.length()-s1.length())/finalString.length());
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{

String s = "aabbaaaabba";
String tString =new String();
int i=0;
String finalString=null;
while(i<s.length()/2) {
char c = s.charAt(i);
tString = tString+new StringBuilder(c+"").toString();
if(s.lastIndexOf(tString)!=i) {
finalString = tString;
}
i++;
}
System.out.println(finalString);
String s1= s.replaceAll(finalString, "");
if(s1.equals("")) {
System.out.println(s.length()/finalString.length());
}else {
System.out.println((s.length()-s1.length())/finalString.length());
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static boolean isPeriodic(String input) {
for (int charIndex = 1; charIndex <= input.length() / 2; charIndex++) {
String contentAfterSplit = String.join("", input.split(input.substring(0, charIndex)));
if (contentAfterSplit.equals(""))
return true;
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static boolean isPeriodic(String input) {
for (int charIndex = 1; charIndex <= input.length() / 2; charIndex++) {
String contentAfterSplit = String.join("", input.split(input.substring(0, charIndex)));
if (contentAfterSplit.equals(""))
return true;
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Go:

``````func isPattern(s, pat string) bool {
l := len(s)
p := len(pat)
if l%p != 0 {
return false
}
for i := 0; i < p; i++ {
for j := 0; j < l; j += p {
if s[i+j] != pat[i] {
return false
}
}
}
return true
}

func findPattern(s string) (int, string) {
l := len(s)
if l < 2 {
return l, s
}
for i := 1; i < l/2+1; i++ {
if l%i != 0 {
continue
}
p := s[:i]
if isPattern(s[i:], p) {
return l / i, p
}
}
return 1, s
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

N^2 C++ solution, with constrain that the pattern should start from first character and end with the last:

``````pair<string, int> findPattern(const string &s)
{
int n = s.length();
int divisor = 2;

while (divisor <= n)
{
if (n % divisor == 0)
{
int patternLen  = n / divisor;
int repetitions = n / patternLen;
bool match = true;

for (int i = 1; i < repetitions; ++i)
{
for (int j = 0; j < patternLen; ++j)
{
if (s[j] != s[i * patternLen + j])
{
match = false;
break;
}
}

if (!match)
break;
}

if (match)
return {s.substr(0, patternLen), repetitions};
}

++divisor;
}

return {"", 0};
}``````

Comment hidden because of low score. Click to expand.
-1
of 5 vote

LeetCode 459. Repeated Substring Pattern

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````/// The question is wrong, should return 6x in the example xxxxxx
static String getPeriodic(String input) {
int length = input.length();
String subString = "";
String expanded = "";
for(int i =0;  i<length/2; i++)
{
expanded = "";
subString = "";
if(length%(i+1)==0)
{
subString = input.substring(0,i+1);
for (int j=0; j< length/(i+1); j++) {
expanded = expanded + subString ;
}
if (input.equals(expanded))
{
return (length/subString.length()+subString);
}
}
}
return "";``````

}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.