LeetCode75: Greatest Common Divisor of Strings

Introduction

The Greatest Common Divisor of Strings problem is a fascinating blend of string manipulation and mathematical logic, commonly featured in coding interviews and the LeetCode 75 study plan. In this challenge, you’re given two non-empty strings, str1 and str2, and your task is to find the largest string x such that both str1 and str2 can be constructed by repeating x one or more times.

This “string GCD” mimics the idea of the greatest common divisor from arithmetic, but applies it to repeated string patterns instead of numbers. To solve this problem, you’ll need to combine insights from modular string patterns, efficient string matching, and the classic Euclidean algorithm.

Given two strings str1 and str2, return the greatest common divisor (GCD) string of the two.

A string x is called a divisor of str if str can be formed by concatenating x one or more times.

Find the largest string x such that:

• Both str1 and str2 are divisible by x
• If no such string exists, return an empty string ("")

Example 1:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Constraints:

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

Python Solution

from math import gcd

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ""
        max_length = gcd(len(str1), len(str2))
        return str1[:max_length]

Step-by-Step Explanation

Step 1: Import GCD Function

from math import gcd

• The built-in gcd function from Python’s math module is used to find the greatest common divisor of the string lengths.

Step 2: Define the Function

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:

• Method gcdOfStrings takes two strings str1 and str2 as input.

Step 3: Check Compatibility Using Concatenation

        if str1 + str2 != str2 + str1:
            return ""

• This clever condition checks if str1 and str2 share the same repeating pattern.
• If they don’t match when concatenated in both orders, there is no common base string, so return "".

Step 4: Find the GCD of String Lengths

        max_length = gcd(len(str1), len(str2))

• This finds the length of the largest possible repeating substring that could divide both str1 and str2.

Step 5: Return the GCD String

        return str1[:max_length]

• The GCD string will always be the prefix of either string with length equal to gcd(len(str1), len(str2)).

Why the Concatenation Check Works

If two strings str1 and str2 have the same repeating pattern, then:

str1 + str2 == str2 + str1

Otherwise, they can’t have a common base divisor string.

Time and Space Complexity

• Time Complexity:O(m + n)
  • For concatenation and GCD computation, where m and n are lengths of the two strings.
• Space Complexity:O(1)
  • Only a few extra variables are used.

This solution uses a string theory trick combined with the mathematical GCD to efficiently find the greatest common divisor of strings. If both strings can be built from the same repeating substring, the problem is reduced to finding the GCD of their lengths.

Related Read

Greatest Common Divisor of Strings