# O(|B|+|A|) Java Solution

• ``````class Solution {
public int repeatedStringMatch(String A, String B) {
int lenA = A.length();
int lenB = B.length();

if(lenA>=lenB) {
if(A.contains(B)) return 1;
else if((A+A).contains(B)) return 2;
else return -1;
}

int countSubstr = 0;
int i,j,firstI = -1;

for(i=0,j=0;i<lenB;i++)
{
if(B.charAt(i)==A.charAt(j)) {
j++;
if(j==lenA) {
j=0;
countSubstr++;
if(firstI==-1) firstI=i-lenA+1;
}
}
}

if(countSubstr==0) {
if((A+A).contains(B)) return 2;
else return -1;
}
else  {
if(firstI>0) {
String Asplit=B.substring(countSubstr*lenA+firstI,lenB)+B.substring(0,firstI);
if(Asplit.equals(A)) return countSubstr+2;
else return -1;
}
else {
if(countSubstr*lenA==lenB) return countSubstr;
else if((lenB - countSubstr*lenA < lenA) && B.substring(countSubstr*lenA,lenB).equals(A.substring(0,lenB - countSubstr*lenA))) return countSubstr+1;
else return -1;
}
}
}
}
``````

• Surely you're joking? Already the first `A.contains(B)` isn't O(|B|+|A|).

• Not sure of the Java implementation , but A.contain(B) can be implemented in O(|A|+|B|) time, and there are constant calls to it.

• @davinci.leo Can be but isn't.

• Got your point then. When saying O(|A|+|B|) i assumed java had optimum implementation for contains. BTW what is implementation's runtime order ?

• Thanks for pointing this out.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.