LeetCode 1071 - Greatest Common Divisor of Strings

The problem asks us to find the greatest common divisor (GCD) of two strings. In this context, a string t divides another string s if s can be formed by concatenating t multiple times. The goal is to find the largest string x that divides both str1 and str2.

leetcodeeasymathstring

LeetCode Problem 1071

Difficulty: 🟢 Easy
Topics: Math, String

Solution

Problem Understanding

The problem asks us to find the greatest common divisor (GCD) of two strings. In this context, a string t divides another string s if s can be formed by concatenating t multiple times. The goal is to find the largest string x that divides both str1 and str2.

The input consists of two non-empty strings, str1 and str2, each containing only uppercase English letters. The expected output is the string x that is the longest common divisor of both strings, or an empty string if no such string exists.

The constraints tell us the input strings can be up to length 1000. This means that brute-force approaches that try every substring combination could be inefficient, so we need an approach that scales well with the string length.

Important edge cases include:

  1. Strings with no common divisors at all, e.g., "LEET" and "CODE".
  2. One string being a repetition of another, e.g., "ABABAB" and "ABAB".
  3. Strings that are similar in pattern but differ slightly, e.g., "AAAAAB" and "AAA".

We must handle these cases without errors and return the correct longest common divisor string or an empty string.

Approaches

Brute Force

The brute-force approach would involve generating all possible prefixes of the shorter string and checking if each prefix divides both strings. For each candidate prefix, we would check by repeated concatenation whether it forms the original strings. This is correct because the GCD of strings must be a prefix of both strings, but it is too slow because we could be checking up to min(len(str1), len(str2)) prefixes and concatenating strings multiple times, resulting in O(n * m) operations for each check.

Optimal Approach

The key insight is that the problem mirrors the numeric GCD problem. If we can find the lengths of str1 and str2 that allow a common repeating substring, the length of the GCD string is the numeric GCD of len(str1) and len(str2).

We first check if str1 + str2 == str2 + str1. If this condition fails, there is no common repeating string. If it passes, the greatest common divisor string has length gcd(len(str1), len(str2)), and we can return the prefix of this length from either string. This works because string repetition is commutative only if they share a common base string.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(n + m) Check all prefixes by concatenation
Optimal O(n + m) O(1) Use string concatenation check and numeric GCD

Algorithm Walkthrough

  1. Concatenate the strings in both orders: str1 + str2 and str2 + str1.
  2. Check if the concatenated results are equal. If they are not, return an empty string because no common divisor exists.
  3. Compute the numeric GCD of len(str1) and len(str2) using Euclidean algorithm.
  4. Return the prefix of str1 with length equal to the numeric GCD.

Why it works: The concatenation check ensures that the strings are multiples of a common base. The numeric GCD gives the largest length that evenly divides both string lengths. Taking the prefix of that length ensures we get the largest possible string divisor.

Python Solution

from math import gcd

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # Check if there exists a common divisor by concatenation commutativity
        if str1 + str2 != str2 + str1:
            return ""
        # Compute the length of the greatest common divisor
        length_gcd = gcd(len(str1), len(str2))
        # Return the prefix of str1 with length equal to length_gcd
        return str1[:length_gcd]

The code first verifies that a common string divisor exists using the concatenation property. Then it uses the built-in gcd function from Python's math library to calculate the numeric GCD of string lengths. Finally, the correct prefix is returned as the greatest common divisor string.

Go Solution

import "math"

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

func gcdOfStrings(str1 string, str2 string) string {
    if str1+str2 != str2+str1 {
        return ""
    }
    lengthGCD := gcd(len(str1), len(str2))
    return str1[:lengthGCD]
}

In Go, we implement a custom numeric GCD function because the standard library does not provide one for integers. We use a for loop and the modulo operator to find the GCD, then return the prefix slice of str1.

Worked Examples

Example 1: str1 = "ABCABC", str2 = "ABC"

Concatenate: "ABCABCABC" vs "ABCABCABC" → equal

GCD of lengths: gcd(6, 3) = 3

Return prefix: "ABC"

Example 2: str1 = "ABABAB", str2 = "ABAB"

Concatenate: "ABABABABAB" vs "ABABABABAB" → equal

GCD of lengths: gcd(6, 4) = 2

Return prefix: "AB"

Example 3: str1 = "LEET", str2 = "CODE"

Concatenate: "LEETCODE" vs "CODELEET" → not equal

Return ""

Example 4: str1 = "AAAAAB", str2 = "AAA"

Concatenate: "AAAAABAAA" vs "AAAAAA" → not equal

Return ""

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Concatenation comparison is linear in string lengths; computing GCD is O(log(min(n,m)))
Space O(1) We only store a few integer values; concatenation check is transient and can be optimized further if needed

The optimal solution is linear in practice because the concatenation equality check scans each character once, and the GCD computation is negligible compared to string scanning.

Test Cases

# Provided examples
assert Solution().gcdOfStrings("ABCABC", "ABC") == "ABC"  # common divisor exists
assert Solution().gcdOfStrings("ABABAB", "ABAB") == "AB"  # common divisor exists
assert Solution().gcdOfStrings("LEET", "CODE") == ""      # no common divisor
assert Solution().gcdOfStrings("AAAAAB", "AAA") == ""     # no common divisor

# Edge tests
assert Solution().gcdOfStrings("A", "A") == "A"           # single character strings
assert Solution().gcdOfStrings("ABABABAB", "ABAB") == "AB" # longer repetitive pattern
assert Solution().gcdOfStrings("XYZ", "XYZXYZXYZ") == "XYZ" # str1 shorter than str2
assert Solution().gcdOfStrings("ABC", "DEF") == ""         # completely different strings
assert Solution().gcdOfStrings("AAAAAAAAAA", "AAAA") == "A" # multiple repetitions of the same character
Test Why
"ABCABC", "ABC" Validates normal common divisor
"ABABAB", "ABAB" Checks divisor with overlapping repetitions
"LEET", "CODE" Confirms function returns empty for no divisor
"AAAAAB", "AAA" Tests prefix similarity but different overall
"A", "A" Handles minimal length strings
"ABABABAB", "ABAB" Tests longer repetition patterns
"XYZ", "XYZXYZXYZ" Tests shorter string fully contained in longer
"ABC", "DEF" Confirms completely different strings return empty
"AAAAAAAAAA", "AAAA" Tests repeated single character strings

Edge Cases

  1. No common divisor at all: When the strings share no repeated pattern, e.g., "LEET" and "CODE". The algorithm handles this by checking str1 + str2 != str2 + str1 and returning an empty string, preventing unnecessary computation.
  2. Single character strings: Strings of length 1, like "A" and "A", are handled correctly because the concatenation check still applies, and the GCD of 1 and 1 is 1, returning the single character.
  3. One string is multiple of the other: Cases like "XYZ" and "XYZXYZXYZ" require checking that the longer string is a repetition of the shorter. The concatenation property ensures that only strings that truly share a base pattern pass, and the GCD of lengths gives the correct divisor length.