CareerCup

/*
Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

For example, with A = "abcd" and B = "cdabcdab".

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

Note:
The length of A and B will be between 1 and 10000.
*/



console.log(isRepeat('abcd','bcdabcdab'));

function isRepeat(seed, target){
  let tmp = seed;
  let count = 1;
  for (; tmp.length < target.length; count++) {
    tmp+= seed
  }
  if (tmp.indexOf(target) !==-1) {
     return count;
  }
  return -1;
}


/*
Complixity is o(n).
you can always use KMP algorithem to implement indexOf which has o(n)


*/

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

count=0
while True:
    count+=1
    if B in A*count:
        print(count)
        break

    if count>1000:
        print(-1)
        break

int getCount(String A, String B) {
int startIndex = B.indexOf(A);

int count = B.length() / A.length();
if (startIndex > 0) {
count++;
}
return count;
}

int getCount(String A, String B) {
        int startIndex = B.indexOf(A);

        int count = B.length() / A.length();
        if (startIndex > 0) {
            count++;
        }
        return count;
    }

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

Time complexity: O(n) where n is the length of aString

def repeatingStringCheck(aString, bString):
    try: 
        n = aString.index(bString[0])
    except ValueError:
        return False
    while len(aString) < len(bString) + n:
        aString += aString
    return bString in aString

search for the substring starting index of A in string B and return the i+1 that will be the count

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));
}
}

I think we can use KMP algorithm to solve it, and it takes linear time to solve it.

public static void main(String[] args) {

		String A = "abcd";
		String B = "cdabcdab";
		String temp = "";
		
		int len = B.length() / A.length();
		
		for(int i=0; i<len; i++) {
			temp = temp + A;
		}

		while(true) {
			if(temp.contains(B)) {
				System.out.println(len);
				break;
			}else {
				len++;
				temp = temp+A;
			}
		}
	}

public static void main(String[] args) {

		String A = "abcd";
		String B = "cdabcdab";
		String temp = "";
		
		int len = B.length() / A.length();
		
		for(int i=0; i<len; i++) {
			temp = temp + A;
		}

		while(true) {
			if(temp.contains(B)) {
				System.out.println(len);
				break;
			}else {
				len++;
				temp = temp+A;
			}
		}
	}