Find the largest string that can be repeated to build both given strings exactly.
Given two strings str1 and str2, find the largest string x such that both str1 and str2 can be formed by repeating x one or more times.
If no such string exists, return an empty string.
A string x is said to divide a string s if s can be written as x concatenated with itself some number of times.
Return the greatest common divisor string of str1 and str2 — that is, the longest string that divides both.
str1 and str2."".1 <= str1.length, str2.length <= 1000str1 and str2 consist of lowercase English letters only.Example 1
Input
str1 = "ABCABC", str2 = "ABC"
Output
"ABC"
Explanation
"ABC" repeated twice makes "ABCABC", and repeated once makes "ABC".
Example 2
Input
str1 = "ABABAB", str2 = "ABAB"
Output
"AB"
Explanation
"AB" repeated 3 times makes "ABABAB", and repeated 2 times makes "ABAB".
Example 3
Input
str1 = "LEET", str2 = "CODE"
Output
""
Explanation
There is no non-empty string that can be repeated to form both strings exactly.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.