Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
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
}
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;
}
}
}
}
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;
}
#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);
}
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
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;
}
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()));
}
}
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()));
}
}
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;
}
/**
* 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));
}
}
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')
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')
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',
'asdasdasdsadsadsadsad',
'ab'*50,
'asd'*20
]
for each in test_cases:
findPattern(each)
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',
'asdasdasdsadsadsadsad',
'ab'*50,
'asd'*20
]
for each in test_cases:
findPattern(each)
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)
throw new NoSuchObjectException("Pattern not found!!!");
else
return input.substring(0,repeatPos);
}
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.")
}
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.")
}
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.")
}
{{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;
}}}
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;
}
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
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"))
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
{
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
}
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"));
}
}
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'))
#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;
}
#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;
}
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;
}
#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;
}
#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;
}
#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;
}
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");
}
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");
}
{
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());
}
}
}
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());
}
}
{
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());
}
}
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
}
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};
}
/// 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 "";
}
KMP prefix table algorithm can help
- koustav.adorable March 01, 2019