Domain 1EasyCORE

Greatest Common Divisor of Strings

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`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

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 str1 and str2 can 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

  1. Concatenate and Compare: First, concatenate str1 and str2 in both possible orders (str1 + str2 and str2 + str1). If they are not equal, return an empty string because there is no common divisor.
  2. Find GCD Length: Use the Euclidean algorithm to find the greatest common divisor of the lengths of str1 and str2. This gives us the length of the largest possible common divisor string.
  3. Extract Common Divisor: The substring from the start of either str1 or str2 up 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 str1 and str2, 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 + str2 is not equal to str2 + str1, the function returns an empty string.
  • Equal Strings: If str1 and str2 are 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.