Find the largest string that can be repeated to build both given strings exactly.
Problem
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.
Goal
Return the greatest common divisor string of str1 and str2 — that is, the longest string that divides both.
Input Format
- Two non-empty strings
str1andstr2. - Each string contains lowercase English letters.
Output Format
- Return the longest string that divides both inputs.
- If no common divisor string exists, return
"".
Constraints
1 <= str1.length, str2.length <= 1000str1andstr2consist 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".
Show 1 more example
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
Unlock deeper context for this problem
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.