## Google Interview Question

Software Engineers**Country:**United States

```
public static int solve(String strA, String strB){
final Set<Character> chars = strB.chars().distinct().mapToObj(e -> (char)e).collect(Collectors.toSet());
if(chars.stream().anyMatch(aChar -> !strA.contains(aChar.toString()))) return -1;
else if(strA.equals(strB)) return 1;
else if(strA.contains(strB)) return 1;
boolean isSubstr = true;
for (int i = 0; i < strB.length() && strB.length() % strA.length() == 0; i++)
if (strB.charAt(i) != strA.charAt(i % strA.length())) isSubstr = false;
if (strB.length() % strA.length() == 0 && isSubstr) return strB.length() / strA.length();
int index = strB.indexOf(strA);
String leftFragment = "", rightFragment = "";
if(index>0) leftFragment = strB.substring(0, index);
index = strB.lastIndexOf(strA);
if(index > 0) rightFragment = strB.substring(index + strA.length(), strB.length());
if(!leftFragment.isEmpty()){
strB = strA.substring(0, strA.indexOf(leftFragment)) + strB;
}
if(!rightFragment.isEmpty()){
strB = strB + strA.substring(strA.indexOf(rightFragment)+1);
}
if(strA.indexOf(leftFragment) == 0) return -1;
else if(strA.indexOf(rightFragment) == strA.length()-1) return -1;
isSubstr = true;
for (int i = 0; i < strB.length() && strB.length() % strA.length() == 0; i++)
if (strB.charAt(i) != strA.charAt(i % strA.length())) isSubstr = false;
return isSubstr ? strB.length()/strA.length() : -1;
}
```

If B matches repeated A that means B can be written as <S><A...><P> where <S> is any suffix of A including empty suffix, <A...> is A repeated some number of times including zero times and <P> is any prefix of A including empty prefix. Let len(A) = N, len(B) = M then ans is 1 (if non-empty S exists) + number of times A is repeated + 1 (if non-empty P exists):

<S> and <P> can be checked to exist in O(N*N) while individual <A> can be checked in N time and there might be at max ceil(M/N) times <A> in B.

If this pattern is not matched, return -1.

```
public static void main(String[] args) {
String A = "abcd";
String B = "cdabcdabcdabcdab";
String temp = "";
int len = B.length() / A.length();
for(int i=0; i<len; i++) {
temp = temp + A;
}
while(len<=(B.length() / A.length() + 1)) {
if(temp.contains(B)) {
System.out.println(len);
break;
}else {
len++;
temp = temp+A;
}
}
}
```

```
int getCount(String A, String B) {
int startIndex = B.indexOf(A);
int count = B.length() / A.length();
if (startIndex > 0) {
count++;
}
return count;
}
```

Runtime O(m+n), Space O(1)

```
public static int NumOfRepeatsToGetSubstring(string i_A, string i_B)
{
int count = 1;
int a = 0, b = 0;
while (b < i_B.Length)
{
if (i_A[a] == i_B[b])
{
++b;
}
else if (count > 1)
{
count = -1;
break;
}
++a;
if (a == i_A.Length)
{
a = 0;
++count;
}
}
return count;
}
```

```
The test string never needs to be longer than A + B + A.
function getRepetitions(A, B) {
var test = "", repetitions = 0, max;
if (A.length < B.length)
max = B.length + (A.length * 2);
else
max = A.length * 2;
while (test.length <= max) {
test += A;
repetitions++;
if (test.indexOf(B) != -1) { // I'm not sure if including test.length >= B.length would improve performance here
return repetitions;
}
}
return -1;
}
```

public class Main {

public static void main(String[] args) {

System.out.println(repSubstring("abcd","da"));

}

public static int repSubstring(String a, String b) {

if(a.length() == 0 || b.length() == 0)

return -1;

if(b.length() < a.length()) {

if(a.contains(b))

return 1;

}

return checkSubstring(a, a.concat(a),b,2);

}

public static int checkSubstring(String a, String newA, String b, int n) {

if(newA.length() > b.length()) {

if(newA.contains(b))

return n;

else return -1;

}

return checkSubstring(a,newA.concat(a),b,n+1);

}

}

import java.io.*;

import java.util.*;

class Solution {

static int repeatedStringMatch(String A, String B)

{

int m = A.length();

int n = B.length();

int count;

boolean found = false;

for (int i = 0; i < m; ++i) {

int j = i;

int k = 0;

count = 1;

while (k < n && A.charAt(j) == B.charAt(k)) {

if (k == n - 1) {

found = true;

break;

}

j = (j + 1) % m;

// if j = 0, it means we have repeated the

// string

if (j == 0)

++count;

k += 1;

}

if (found)

return count;

}

return -1;

}

public static void main(String[] args)

{

String A = "abcd", B = "cdabcdab";

// Function call

System.out.println(repeatedStringMatch(A, B));

}

}

- Aiman October 11, 2019