algoadvance

Leetcode 1071 - Greatest Common Divisor of Strings

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

A string x divides string y if and only if y is equal to x concatenated some number of times. For example, “abc” divides “abcabc” but not “abca”.

Clarifying Questions

  1. What is the input format?
    • The inputs are two non-empty strings str1 and str2.
  2. What is the output?
    • The output is the greatest common divisor string x which is the largest string that can divide both str1 and str2.
  3. Are there any constraints on the length of the input strings?
    • No specific constraints are mentioned, but typical constraints for such problems apply (e.g., 1 <= len(str1), len(str2) <= 1000).

Strategy

To solve this problem:

  1. GCD Approach: The idea is inspired by the mathematical GCD (Greatest Common Divisor).
    • If a string x divides both str1 and str2, then it must also divide their concatenations in any order, i.e., x should divide both str1 + str2 and str2 + str1.
    • Thus, the first thing to check is if str1 + str2 == str2 + str1. If not, return an empty string as there’s no common divisor.
    • If they are a match, the length of the GCD string should be gcd(len(str1), len(str2)).
  2. Helper Functions: We will create helper functions to:
    • Compute the GCD of two numbers.
    • Use the GCD length to extract the divisor substring from any of the input strings and return it.

Code

import math

def gcd_of_strings(str1, str2):
    # Check if str1 + str2 is equal to str2 + str1
    if str1 + str2 != str2 + str1:
        return ""

    # Find the GCD of the lengths of str1 and str2
    gcd_length = math.gcd(len(str1), len(str2))
    
    # The GCD string is the substring of str1 from 0 to gcd_length
    return str1[:gcd_length]

# Example Usage
str1 = "ABCABC"
str2 = "ABC"
print(gcd_of_strings(str1, str2))  # Output: "ABC"

Time Complexity

Therefore, the overall time complexity is (O(len(str1) + len(str2))).

Try our interview co-pilot at AlgoAdvance.com