Leetcode – Greatest Common Divisor of Strings Solution

Spread the love

The intersection of mathematics and computer science has always been a fertile ground for intriguing problems. Among these, the ones that merge number theory with string processing often present unique challenges, requiring a blend of mathematical insight and algorithmic ingenuity. The “Greatest Common Divisor of Strings” problem on Leetcode is an exemplar of this class. In this article, we will thoroughly explore the problem, understand the foundational mathematics, and craft elegant solutions in Python.

Table of Contents:

  1. Problem Statement
  2. Mathematical Intuition
  3. Problem Solving Techniques
  4. Python Implementations
  5. Efficiency Analysis
  6. Summing Up

1. Problem Statement:

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

Example:

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

2. Mathematical Intuition:

To tackle this problem, we first need to understand what it means for one string to divide another. A string x divides y if you can repeat x some number of times to get y. This is analogous to how integers divide one another.

For instance, the number 2 divides 8 because 2×4=8. Similarly, the string “ab” divides “abab” because “ab” repeated twice yields “abab”.

Drawing from number theory, if gcd(a, b) is the greatest common divisor of a and b, then for any integers x and y, gcd(a * x, b * y) will be gcd(a, b) * gcd(x, y). This property can be applied to our string problem as well.

3. Problem Solving Techniques:

  1. Brute Force: Generate all substrings of str1 and str2 and check for common divisors.
  2. Recursive Approach: Based on Euclidean algorithm for GCD, keep subtracting the smaller string from the larger one until you either find the GCD or conclude there isn’t one.

4. Python Implementations:

1. Brute Force Approach:

This method isn’t efficient for larger strings but lays the groundwork for understanding the problem.

def gcdOfStrings_brute(str1, str2):
    for i in range(min(len(str1), len(str2)), 0, -1):
        if len(str1) % i == 0 and len(str2) % i == 0:
            if str1[:i] * (len(str1) // i) == str1 and str1[:i] * (len(str2) // i) == str2:
                return str1[:i]
    return ""

2. Recursive Approach:

Building on the Euclidean algorithm for finding the GCD of two numbers:

def gcdOfStrings(str1, str2):
    # Base case: if str2 is empty, str1 is the answer
    if not str2:
        return str1
    
    # If str1 starts with str2, then the problem can be reduced
    if str1.startswith(str2):
        return gcdOfStrings(str1[len(str2):], str2)
    else:
        return ""

5. Efficiency Analysis:

  • Brute Force Approach: This approach tries all possible combinations and has exponential complexity. For strings of length n, the worst-case time complexity can be considered O(n^2).
  • Recursive Approach: This method is much faster and has a time complexity analogous to the Euclidean algorithm for GCD, which is O(log ⁡min⁡(a,b)). Here, the complexity can be approximated as linear with respect to the size of the shorter string, i.e., O(n), where n is the length of the shorter string.

6. Summing Up:

The “Greatest Common Divisor of Strings” problem is a fantastic blend of mathematical theory and practical coding. Understanding the foundations of number theory, particularly the properties of the GCD, is key to crafting an efficient solution. While the brute force approach offers a foundation, the recursive approach, inspired by the Euclidean algorithm, demonstrates the power of algorithmic thinking.

Leave a Reply