We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Greatest Common Divisor of Strings

Number: 1146

Difficulty: Easy

Paid? No

Companies: Google, Microsoft, Amazon, Meta, Bloomberg, TikTok, Apple, Yahoo, Adobe

Problem Description

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2. A string t divides another string s if s can be constructed by concatenating one or more copies of t.

Key Insights

  • The necessary condition for a common divisor string is that str1 + str2 must equal str2 + str1.
  • The length of the candidate divisor string must be a divisor of both string lengths.
  • Using the greatest common divisor (gcd) of the lengths of str1 and str2 gives the length of the largest possible candidate.
  • Once a candidate is found, it can be verified by checking if repeating it forms the original strings.

Space and Time Complexity

Time Complexity: O(n + m), where n and m are the lengths of str1 and str2 respectively. Space Complexity: O(n + m), primarily for storage of the input strings and the resulting substring.

Solution

The solution first checks if str1 + str2 equals str2 + str1; if not, no common divisor exists and an empty string is returned. Otherwise, the algorithm computes the gcd of the lengths of str1 and str2. The substring of str1 up to this gcd length is the common divisor string since repeating it forms both str1 and str2.

Code Solutions

def gcd(a, b):
    # Compute the greatest common divisor using the Euclidean algorithm
    while b:
        a, b = b, a % b
    return a

def gcdOfStrings(str1, str2):
    # Check if concatenating the strings in different orders gives the same result
    if str1 + str2 != str2 + str1:
        return ""
    # Compute the gcd of the lengths of str1 and str2
    gcd_length = gcd(len(str1), len(str2))
    # The substring of str1 with length equal to gcd_length is the greatest common divisor string
    return str1[:gcd_length]

# Example usage:
print(gcdOfStrings("ABCABC", "ABC"))  # Output: "ABC"
← Back to All Questions