Repeated String Match

Moderate

0/80

1 upvote

Asked in company

Problem statement

You are given two strings, 'a' and 'b'.

Your task is to find the minimum number of times you need to repeat string 'a' such that string 'b' becomes a substring of the resulting string. If it's impossible for 'b' to be a substring of a repeated 'a', you should return -1.

For example, repeating "abc" 3 times results in the string "abcabcabc".

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains the string 'a'.

The second line of input contains the string 'b'.

Output Format:

Print a single integer representing the minimum number of repetitions of 'a' required, or -1 if it's impossible.

Note:

Repeating a string 0 times results in an empty string.

The strings 'a' and 'b' consist of lowercase English letters.

Sample Input 1:

abcd
cdabcdab

Sample Output 1:

Explanation for Sample 1:

We repeat string 'a' ("abcd") three times to get "abcdabcdabcd".
The string 'b' ("cdabcdab") is a substring of this resulting string. Two repetitions ("abcdabcd") are not enough.

Sample Input 2:

a
aa

Sample Output 2:

Explanation for Sample 2:

Repeating 'a' ("a") two times gives "aa". The string 'b' ("aa") is a substring (in this case, equal to) the result.

Expected Time Complexity:

The expected time complexity is O(N * M), where N is the length of string 'a' and M is the length of string 'b'. Using efficient substring search algorithms, this can be improved to O(N+M).

Constraints:

1 <= a.length, b.length <= 10^4
'a' and 'b' consist of lowercase English letters.

Time limit: 1 sec

Approaches (1)

Approach 1

Repeated String Match

Time Complexity

The expected time complexity is O(N * M), where N is the length of string 'a' and M is the length of string 'b'. Using efficient substring search algorithms, this can be improved to O(N+M).

Space Complexity

(100% EXP penalty)

Repeated String Match

Console