We say a string t divides a string s if s is t written one or more times in a row (s = t + t + ... + t).
You get two strings str1 and str2. Find the longest string x that divides both of them, and return it. If there is no such string, return an empty string.
Examples
Example 1:
Input: str1 = "XYXYXY", str2 = "XYXY"
Output: "XY"
Explanation: "XYXYXY" is "XY" three times and "XYXY" is "XY" two times. "XY" is the longest string that works.
Example 2:
Input: str1 = "ABCDEF", str2 = "ABC"
Output: ""
Explanation: Writing "ABC" repeatedly gives "ABCABC", not "ABCDEF". No string divides both, so the answer is an empty string.
Example 3:
Input: str1 = "PQRPQR", str2 = "PQRPQRPQR"
Output: "PQR"
Explanation: "PQR" written 2 times gives the first string, and 3 times gives the second string.