Find smallest string x that can produce two given strings if repeated 0 or n times

Viewed 281

I was asked this question in a coding challenge but my solution passed 8/14 test cases and couldn't solve it 100%. I need in understand the logic behind the question. My approach was to find out if concatenating t 0 or n times can give you s. If so, I return the longest repeating substring of t.

Given string s and string t, find the length of the smallest string x such that if x is concatenated any number of times, we get both s and t. If this is not possible return -1;

Example 1:

s = bcdbcdbcd
t = bcdbcd

If String t is concatenated twice, the result bcdbcdbcdbcd > s so s is not divisible by t. Return -1

Example 2:

s = bcdbcdbcdbcd
t = bcdbcd

If String t is concatenated twice, the result bcdbcdbcdbcd = s, so s is divisible by t. The smallest string x that can be concatenated to get both s and t is bcd. Return its length, 3.

Example 3:

s = lrbb
t = lrbb

If String lrbb is concatenated once, we get string s and string t. Return its length, 4.

Example 4:

s = rbrb
t = rbrb

If String rb is concatenated twice, we get string s and string t. Return its length, 2.

1 Answers

As the question says, x need not be identical to t. Try the shortest repeating substring of s and see if that divides t.

Related