WHAT TO KNOW<!DOCTYPE html>
LeetCode: 1071. Greatest Common Divisor of Strings
<br> body {<br> font-family: sans-serif;<br> }<br> h1, h2, h3 {<br> text-align: center;<br> }<br> img {<br> display: block;<br> margin: 20px auto;<br> max-width: 100%;<br> }<br> code {<br> font-family: monospace;<br> background-color: #eee;<br> padding: 5px;<br> border-radius: 3px;<br> }<br> pre {<br> background-color: #eee;<br> padding: 10px;<br> border-radius: 5px;<br> }<br>
LeetCode: 1071. Greatest Common Divisor of Strings
Introduction
The "Greatest Common Divisor of Strings" problem on LeetCode is a fun and intriguing challenge that explores the concept of string divisibility and the greatest common divisor (GCD) in a unique way. This problem tests your understanding of string manipulation, recursion, and the core principles behind GCD calculations.
In this article, we'll delve into the problem statement, break down the key concepts, explore different approaches to solving it, and provide detailed code examples in Python and JavaScript.
Problem Statement
You are given two strings,
str1
and
str2
. The greatest common divisor (GCD) of strings
str1
and
str2
is the longest string that is a divisor of both
str1
and
str2
. A string
s
is a divisor of string
t
if
t
is formed by concatenating multiple copies of
s
.
For example,
str1 = "ABCABC"
and
str2 = "ABC"
. The GCD is
"ABC"
. For
str1 = "ABABAB"
and
str2 = "ABAB"
, the GCD is
"AB"
.
Return the greatest common divisor string of
str1
and
str2
. If no common divisor string exists, return an empty string.
Key Concepts
-
String Divisibility: A string
sis a divisor of stringtiftcan be formed by repeatingsmultiple times.- Greatest Common Divisor (GCD): The GCD of two strings is the longest string that divides both strings.
-
Euclidean Algorithm: This efficient algorithm is used to find the GCD of two integers. We'll adapt this concept for strings.
Solution Approach
### 1. Brute Force (Inefficient)The brute force approach involves iterating through all possible substrings of the shorter string. For each substring, we check if it's a divisor of both strings. This method is inefficient, especially for long strings, as it has a high time complexity.
def gcdOfStrings_brute_force(str1, str2):
"""
Finds the GCD of two strings using a brute force approach.
Args:
str1: The first string.
str2: The second string.
Returns:
The greatest common divisor string.
"""
min_len = min(len(str1), len(str2))
for i in range(min_len, 0, -1):
substring = str1[:i]
if is_divisor(str1, substring) and is_divisor(str2, substring):
return substring
return ""
def is_divisor(string, substring):
"""
Checks if a substring is a divisor of a string.
Args:
string: The main string.
substring: The potential divisor.
Returns:
True if the substring is a divisor, False otherwise.
"""
if len(string) % len(substring) != 0:
return False
return string == substring * (len(string) // len(substring))
2. Euclidean Algorithm Adaptation (Efficient)
We can adapt the Euclidean Algorithm to find the GCD of strings. The core idea is:
-
Base Case: If one string is empty, the GCD is the other string.
- Recursive Step: If both strings are non-empty, we recursively find the GCD of the shorter string and the difference between the longer string and the shorter string.
def gcdOfStrings_euclidean(str1, str2):
"""
Finds the GCD of two strings using the Euclidean Algorithm.
Args:
str1: The first string.
str2: The second string.
Returns:
The greatest common divisor string.
"""
if str2 == "":
return str1
return gcdOfStrings_euclidean(str2, str1[len(str2):])
3. String Concatenation and Comparison (Efficient)
This approach is based on the observation that if a string
s
is a common divisor of
str1
and
str2
, then it must also be a divisor of their concatenation:
str1 + str2
. This allows us to efficiently check for the GCD using string concatenation and comparison.
def gcdOfStrings_concatenation(str1, str2):
"""
Finds the GCD of two strings using string concatenation and comparison.
Args:
str1: The first string.
str2: The second string.
Returns:
The greatest common divisor string.
"""
concatenated = str1 + str2
if len(concatenated) == len(str1) + len(str2):
return "" # No common divisor
for i in range(1, len(concatenated)):
if concatenated[:i] * (len(concatenated) // i) == concatenated:
return concatenated[:i]
return ""
Code Examples
### Python
def gcdOfStrings(str1, str2):
"""
Finds the GCD of two strings using string concatenation and comparison.
Args:
str1: The first string.
str2: The second string.
Returns:
The greatest common divisor string.
"""
concatenated = str1 + str2
if len(concatenated) == len(str1) + len(str2):
return "" # No common divisor
for i in range(1, len(concatenated)):
if concatenated[:i] * (len(concatenated) // i) == concatenated:
return concatenated[:i]
return ""
# Example usage
str1 = "ABCABC"
str2 = "ABC"
gcd = gcdOfStrings(str1, str2)
print(f"GCD of '{str1}' and '{str2}': '{gcd}'")
JavaScript
function gcdOfStrings(str1, str2) {
let concatenated = str1 + str2;
if (concatenated.length === str1.length + str2.length) {
return ""; // No common divisor
}
for (let i = 1; i < concatenated.length; i++) {
if (concatenated.slice(0, i).repeat(concatenated.length / i) === concatenated) {
return concatenated.slice(0, i);
}
}
return "";
}
// Example usage
let str1 = "ABCABC";
let str2 = "ABC";
let gcd = gcdOfStrings(str1, str2);
console.log(`GCD of '${str1}' and '${str2}': '${gcd}'`);
Conclusion
In this article, we explored the LeetCode problem "Greatest Common Divisor of Strings." We learned about string divisibility, the GCD concept, and how to adapt the Euclidean Algorithm for strings. We also discussed different approaches to solving the problem, highlighting the efficiency of the string concatenation method.
By understanding these concepts and techniques, you can confidently tackle similar string manipulation and GCD-related problems in your coding journey.
