Greatest Common Divisor of Strings
The key idea
A common divisor string exists only if str1 + str2 equals str2 + str1. When it does, the longest divisor has length gcd(len(str1), len(str2)), and the answer is the prefix of str1 of that length.
Problem
For two strings s and t, we say "t divides s" if and only if s = t + t + t + ... + t (i.e., t is concatenated with itself one or more times to form s).
Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.
Constraints
- 1 <= str1.length, str2.length <= 1000
- str1 and str2 consist of English uppercase letters.
Examples
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"
Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"
Input: str1 = "LEET", str2 = "CODE"
Output: ""
Complexity
Time: O(n + m) Space: O(n + m)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Math / Number Theory problems
- Add BinaryEASY
- Factorial Trailing ZeroesMEDIUM
- Excel Sheet Column TitleEASY
- Integer to RomanMEDIUM
- Multiply StringsMEDIUM
- Palindrome NumberEASY
- Plus OneEASY
- Reverse IntegerMEDIUM
- Roman to IntegerEASY