Greatest Common Divisor of Strings
Easy · Math · Math · String
Problem
A string t divides a string s when s is t written one or more times in a row: "AB" divides "ABABAB", but "AB" does not divide "ABA".
Given two strings str1 and str2, return the longest string that divides both of them. If no string divides both, return the empty string "".
This is the greatest common divisor of two numbers, carried over to strings: the answer's length turns out to be gcd(len(str1), len(str2)), provided the two strings are built from the same block at all.
Examples
Input: str1 = "ABCABC", str2 = "ABC" Output: "ABC"
"ABC" written twice is str1 and once is str2.
Input: str1 = "ABABAB", str2 = "ABAB" Output: "AB"
"ABAB" does not divide str1 (6 is not a multiple of 4), but "AB" divides both. Its length 2 is gcd(6, 4).
Input: str1 = "LEET", str2 = "CODE" Output: ""
The strings start with different letters, so no block can build both.
Constraints
- 1 <= len(str1), len(str2) <= 1000
- str1 and str2 consist of English uppercase letters
Approaches
- Baseline: try every prefix length — time O(min(m, n) · (m + n)), space O(m + n)
Follow-up
The same ideas give the shortest common multiple of two strings (the first string repeated len2 / gcd times, under the same commuting test), the greatest common divisor of a whole list of strings, and the smallest repeating unit of one string. The use cases below cover all three.
Related problems
Start free on Cariara · Coding problems · System design studio
