Greatest Common Divisor of Strings

Difficulty: Easy | Acceptance: 53.70% | Paid: No Topics: Math, String

For two strings s and t, we say “t divides s” if and only if s = t + … + t (i.e., t is concatenated with itself one or more times).

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

• Examples
• Constraints
• Brute Force
• Mathematical GCD

Examples

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:

""

Example 4

Input:

str1 = "AAAAAB", str2 = "AAA"

Output:

""​​​​​​​

Constraints

1 <= str1.length, str2.length <= 1000
str1 and str2 consist of English uppercase letters.

Brute Force

Intuition We can iterate through all possible lengths of the common divisor string, starting from the smallest length up to the length of the shorter string. For each length, we check if it divides both strings.

Steps

• Find the minimum length min_len between str1 and str2.
• Iterate i from 1 to min_len.
• Check if min_len is divisible by i (to ensure the substring can form the string).
• Extract the candidate substring of length i.
• Check if repeating this candidate len(str1)/i times equals str1 and len(str2)/i times equals str2.
• If both checks pass, update the result.

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        len1, len2 = len(str1), len(str2)
        min_len = min(len1, len2)
        res = ''
        for i in range(1, min_len + 1):
            if len1 % i == 0 and len2 % i == 0:
                candidate = str1[:i]
                if candidate * (len1 // i) == str1 and candidate * (len2 // i) == str2:
                    res = candidate
        return res

Complexity

• Time: O(min(N, M) * (N + M))
• Space: O(N + M)
• Notes: We iterate up to the minimum length and perform string concatenation/comparison at each step.

Mathematical GCD

Intuition If str1 and str2 have a common divisor string x, then str1 + str2 must be equal to str2 + str1. If they are not equal, no common divisor exists. If they are equal, the length of the greatest common divisor string is the GCD of the lengths of str1 and str2.

Steps

• Check if str1 + str2 is equal to str2 + str1. If not, return an empty string.
• Calculate the greatest common divisor (GCD) of the lengths of str1 and str2.
• Return the substring of str1 from index 0 to the calculated GCD length.

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ''
        from math import gcd
        return str1[:gcd(len(str1), len(str2))]

Complexity

• Time: O(N + M)
• Space: O(N + M)
• Notes: Concatenating strings takes O(N+M) time and space. The GCD calculation is O(log(min(N, M))).