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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Greatest Common Divisor of Strings

Difficulty: Easy

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 t one or more times.

Key Insights

  • The greatest common divisor (GCD) of two strings can be determined by finding the longest substring that can be repeated to form both strings.
  • The length of the desired substring must be a divisor of both str1 and str2.
  • If the concatenation of str1 and str2 in both orders is equal, then the GCD string can be derived from the shorter string.

Space and Time Complexity

Time Complexity: O(n + m), where n and m are the lengths of str1 and str2, respectively.
Space Complexity: O(1), as we are using a constant amount of extra space.

Solution

To solve the problem, we can follow these steps:

  1. Calculate the lengths of both strings.
  2. Determine the greatest common divisor (GCD) of the lengths of the two strings.
  3. Use this GCD to extract the potential GCD string from either str1 or str2.
  4. Check if this substring can form both str1 and str2 by verifying if both strings can be constructed by repeating the substring.

Code Solutions

import math

def gcdOfStrings(str1: str, str2: str) -> str:
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    
    len1, len2 = len(str1), len(str2)
    gcd_length = gcd(len1, len2)
    candidate = str1[:gcd_length]
    
    if candidate * (len1 // gcd_length) == str1 and candidate * (len2 // gcd_length) == str2:
        return candidate
    return ""
← Back to All Questions