This post is completed by 5 users

  • 1
 Add to List
Beginner

496. Minimum number of times String A is repeated to such that B is substring of A

Given a string A consisting of n characters and a string B consisting of m characters, write a function that will return the number of times A must be repeated such that B is a substring of the repeated A. If B can never be a substring, return -1.

Example:

A = 'abcd'
B ='cdabcdab'
The function should return 2 because after repeating A 2 more times, getting 'abcdabcdabcd', B is now a substring of A.

You can assume that n and m are integers in the range [1, 1000].

Approach: 

  1. Initialize count = 0.
  2. First check if length of A >= length of B, if not then keep repeating A into the string buffer S until the above condition is not true.
  3. Now at this point length of A >= length of B. So check if B is already a substring of A. If not then append A to string buffer S for one last time, do count++ (why one last time, if B is to be substring of A then then you will find it after this append else B is not substring of A, let's take an example A = "abcd" and B = "cdab", if you repeat A then A = "abcdabcd" and now B is substring of A, the edge cases where B is rotation of A, will be solved if we repeat A one time.) and check if B is substring of A then return count else return -1. 

Output:

String A: abcd, B: cdabcdab
Minimum repetition of A to make B as substring: 2
String A: abcde, B: cdeabcdeabf
Minimum repetition of A to make B as substring: -1

Reference: CareerCup

Related Problems: