This post is completed by 3 users
|Add to List|
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 stated such that B is a substring of the repeated A. If B can never be a substring, return -1.
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].
- Initialize count = 0.
- 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.
- 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.
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