243. Common Text Divisor
A sign painter prints banners by repeating a short tile of letters. A string t divides a string s when s is exactly t written one or more times in a row. Given two strings a and b, return the longest string that divides both of them. If no non-empty string divides both, return the empty string.
For example, a = "pinpin" and b = "pinpinpinpin" have the common divisor "pin" (and also "pinpin", which is longer, so that is the answer). With a = "red" and b = "blue" nothing divides both, so the result is empty.
Both strings contain only lowercase English letters. An efficient solution needs only O(|a| + |b|) time, and should not try every prefix length blindly.
Example 1
- Input:
- a = "mangomango", b = "mangomangomango"
- Output:
- "mango"
- Explanation:
The common unit is mango: the first string repeats it twice and the second three times, and no longer unit divides both.
Example 2
- Input:
- a = "tictac", b = "tic"
- Output:
- ""
- Explanation:
The strings share no repeating unit, because tictac is not made of copies of tic, so the answer is the empty string.
Constraints
1 ≤ a.length, b.length ≤ 1000
a and b consist of lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(|a| + |b|)
- Space
- O(|a| + |b|)