Greatest Common Divisor of Strings

As part of my LeetCode 75 series, I’m diving into fundamental algorithmic problems that enhance problem-solving skills. Today, we explore the problem Greatest Common Divisor of Strings (LeetCode 1071) The problem is a great blend of string manipulation and mathematical concepts, particularly the Greatest Common Divisor (GCD).

Problem Statement

Given two strings str1 and str2, the task is to determine the largest string X that divides both str1 and str2. In other words, X should be the largest string that, when repeated, can form both str1 and str2.

Solution Approach

To solve this problem, we leverage two key insights:

1. If str1 + str2 is not equal to str2 + str1, there is no common divisor string.

2. The length of the GCD string is determined by the Greatest Common Divisor (GCD) of the lengths of str1 and str2.

Implementation in Go

Below is the Go implementation for solving this problem efficiently:

package leetcode_75
import "fmt"

func GreatestCommonDivisorOfStrings() {
    str1 := "ABAB"
    str2 := "ABABAB"
    fmt.Printf("gcdOfStrings(): %v\n", gcdOfStrings(str1, str2))
}

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

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

Complexity Analysis

• Time Complexity: O(N + log(min(len(str1), len(str2))))

• Space Complexity: O(1), as we use only a few additional variables.

Explanation

1. Concatenation Check: If str1 + str2 is not equal to str2 + str1, it means the two strings do not share a common pattern, so we return an empty string.

2. Finding the GCD Length: We compute the GCD of the lengths of str1 and str2.

3. Extracting the GCD String: The prefix of str1 up to the GCD length is the desired result.

Example Walkthrough

Input:

str1 = "ABAB"
str2 = "ABABAB"

Process:

• str1 + str2 = "ABABABABABAB"

• str2 + str1 = "ABABABABABAB" (equal ✅)

• GCD(len("ABAB"), len("ABABAB")) = 2

• The first 2 characters of str1 ("AB") is the GCD string.

Output:

"AB"

Conclusion

This problem demonstrates how mathematical concepts like GCD can be applied to string problems, making it a perfect blend of string manipulation and number theory. Stay tuned for more problems in the LeetCode 75 series!