1071. Greatest Common Divisor of Strings
On This Page
The problem is about finding a greatest common divisor (GCD) of two strings. The term “GCD” might be familiar from mathematics, as the largest number that divides two numbers without leaving a remainder. Here, we extend the idea to strings: a string
x is a GCD of strings
x can be repeatedly appended to itself to obtain
A naive approach would be to find all possible divisors of
str2, and then find the largest common divisor. This would involve generating all substrings of
str2 which is time-consuming and unnecessary.
Observing the problem, we see a similarity with the Euclidean algorithm for calculating the GCD of two numbers. In the Euclidean algorithm, the GCD of two numbers
a > b) is the same as the GCD of
a mod b.
We can extend this logic to strings. If a string
x is a GCD of
str2 can both be written in the form
x + x + ... + x. Therefore,
str1 - str2 (which is similar to
a mod b) should also be expressible in the form
x + x + ... + x.
This observation allows us to use a similar approach to the Euclidean algorithm to solve this problem.
Why finding Greatest common divisor?
In case smallest string consist multiple same parts.
Example: str1 = “ABABAB”, str2 = “ABAB”.
len(str1) = 6, len(str2) = 4. We can’t use whole str2 but common minimum length -> 2.
Here are the high-level steps of the algorithm:
str2is not equal to
str1, return an empty string.
- Otherwise, find the GCD of the lengths of
- Return the prefix substring of
str1with length equal to the GCD.
Here is a Python solution that implements the above algorithm:
class Solution: def gcdOfStrings(self, str1: str, str2: str) -> str: def gcd(a, b): while b != 0: a, b = b, a % b return a if str1 + str2 != str2 + str1: return '' max_substr_len = gcd(len(str1), len(str2)) return str1[:max_substr_len]
gcdOfStrings method, we first check if
str1 + str2 is equal to
str2 + str1. If they are not equal, no common divisor string exists, so we return an empty string. If they are equal, we find the GCD of the lengths of
str2 and return the prefix substring of
str1 with length equal to the GCD.
The gcd method is a standard implementation of the Euclidean algorithm to find the GCD of two numbers.