# 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)](https://leetcode.com/problems/greatest-common-divisor-of-strings/) 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:

```go
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:**

```go
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:**

```go
"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**!