Greatest Common Divisor of Strings

For two strings s and t, we say "t divides s" if and only if s = t + t + t + ... + t + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Examples:

1. str1 = "ABCABC", str2 = "ABC". Output: "ABC"
2. str1 = "ABABAB", str2 = "ABAB". Output: "AB"
3. str1 = "LEET", str2 = "CODE". Output: ""

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of English uppercase letters.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def greatest_common_divisor_string(str1: str, str2: str) -> str:
    """Finds the greatest common divisor string of two strings."""

    # If str1 + str2 is not equal to str2 + str1, then there is no solution
    if str1 + str2 != str2 + str1:
        return ""

    # Find the GCD of the lengths of the two strings
    gcd_length = gcd(len(str1), len(str2))

    # Return the prefix of str1 with length equal to the GCD
    return str1[:gcd_length]

# Example Usage
str1 = "ABCABC"
str2 = "ABC"
result = greatest_common_divisor_string(str1, str2)
print(f"Greatest common divisor string of {str1} and {str2} is: {result}")

str1 = "ABABAB"
str2 = "ABAB"
result = greatest_common_divisor_string(str1, str2)
print(f"Greatest common divisor string of {str1} and {str2} is: {result}")

str1 = "LEET"
str2 = "CODE"
result = greatest_common_divisor_string(str1, str2)
print(f"Greatest common divisor string of {str1} and {str2} is: {result}")

Explanation:

1. GCD Condition:

   • The function first checks if str1 + str2 is equal to str2 + str1. If this condition is not met, it means there is no common divisor string, and the function returns an empty string.

2. GCD Length:

   • If the GCD condition is satisfied, the function calculates the greatest common divisor (GCD) of the lengths of str1 and str2. This GCD represents the length of the potential common divisor string.

3. Extract Divisor:

   • The function extracts the prefix of str1 with a length equal to the calculated GCD. This prefix is the greatest common divisor string.

4. Return Value:

   • The function returns the extracted prefix, which is the largest string that divides both str1 and str2.

Big O Time Complexity:

• GCD Calculation: The time complexity of the gcd function (Euclidean algorithm) is O(log(min(a, b))), where a and b are the lengths of the input strings. This is because the number of steps in the Euclidean algorithm is logarithmic with respect to the smaller of the two numbers.
• String Concatenation and Comparison: The string concatenation str1 + str2 and str2 + str1 takes O(m + n) time, where m and n are the lengths of str1 and str2, respectively. The string comparison also takes O(m + n) time in the worst case.
• String Slicing: The string slicing str1[:gcd_length] takes O(gcd_length) time, which is at most O(min(m, n)).
• Overall: Considering all the steps, the dominant factor is the string concatenation and comparison, which takes O(m + n) time. Therefore, the overall time complexity of the greatest_common_divisor_string function is O(m + n).

Big O Space Complexity:

• GCD Calculation: The gcd function uses constant space, O(1), as it only involves a few variable assignments.
• String Concatenation: The string concatenation str1 + str2 and str2 + str1 creates new strings, each of length m + n, where m and n are the lengths of str1 and str2, respectively. Thus, the space complexity for this step is O(m + n).
• String Slicing: The string slicing str1[:gcd_length] creates a new string of length gcd_length, which is at most O(min(m, n)).
• Overall: Considering all the steps, the dominant factor is the string concatenation, which creates new strings of length m + n. Therefore, the overall space complexity of the greatest_common_divisor_string function is O(m + n).