1071. Greatest Common Divisor of Strings
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 51.8%
Problem Breakdown
The problem asks us to find the largest string x that can divide both input strings str1 and str2. A string t divides another string s if s can be constructed by concatenating t one or more times. The inputs are two strings, str1 and str2, consisting of uppercase English letters. The output should be the largest common divisor string x.
Implicit constraints:
- If there is no common divisor string, return an empty string.
- The lengths of
str1andstr2can range from 1 to 1000 characters.
Intuition
A brute-force approach would involve checking all possible substrings of the shorter string to see if they divide both strings. This is inefficient because it has a time complexity of O(n^3) due to substring checks and concatenations.
The key insight is that if str1 and str2 have a common divisor string, then their concatenation in any order should result in the same string. For example, if x divides both str1 and str2, then str1 + str2 == str2 + str1. This allows us to use the Euclidean algorithm for finding the greatest common divisor (GCD) of two numbers, adapted to strings.
Approach
- Concatenate and Compare: First, concatenate
str1andstr2in both possible orders (str1 + str2andstr2 + str1). If they are not equal, return an empty string because there is no common divisor. - Find GCD Length: Use the Euclidean algorithm to find the greatest common divisor of the lengths of
str1andstr2. This gives us the length of the largest possible common divisor string. - Extract Common Divisor: The substring from the start of either
str1orstr2up to the GCD length is the largest common divisor string.
Complexity Analysis
- Time Complexity: O(n + m), where n and m are the lengths of
str1andstr2, respectively. This is because we perform a single concatenation and comparison, followed by a Euclidean algorithm calculation. - Space Complexity: O(1) for the additional space used, excluding the input strings.
Solution
def gcdOfStrings(str1: str, str2: str) -> str:
# Check if concatenated strings are equal in both orders
if str1 + str2 != str2 + str1:
return ""
# Helper function to compute GCD using Euclidean algorithm
def gcd(a, b):
while b:
a, b = b, a % b
return a
# Find the length of the greatest common divisor string
gcd_length = gcd(len(str1), len(str2))
# Return the substring from str1 up to the GCD length
return str1[:gcd_length]
Edge Cases Handled
- No Common Divisor: If
str1 + str2is not equal tostr2 + str1, the function returns an empty string. - Equal Strings: If
str1andstr2are identical, the entire string is returned as the common divisor. - One String Being a Subset of Another: The GCD length ensures that we get the largest possible substring that divides both strings.