Greatest Common Divisor of Strings

Problem

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

Example 1:

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

Example 2:

1
2
Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Example 3:

1
2
Input: str1 = "LEET", str2 = "CODE"
Output: ""

Solution

Method 1 - Run the gcd

To solve the problem of finding the largest string x such that x divides both str1 and str2, we can employ the greatest common divisor (GCD) concept:

Check Divisibility:
- We need to check if a substring x can repeatedly form both str1 and str2.
GCD of Lengths:
- The length of the largest x that can divide both str1 and str2 will be the greatest common divisor (GCD) of their lengths. This follows from the property of GCD in number theory.
Construct and Verify:
- Construct the substring x using the first GCD(len(str1), len(str2)) characters of either string.
- Verify if this substring can repeatedly form both str1 and str2.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }
        int gcdLength = gcd(str1.length(), str2.length());
        return str1.substring(0, gcdLength);
    }
    
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if not (str1 + str2 == str2 + str1):
            return ""
        def gcd(a: int, b: int) -> int:
            while b:
                a, b = b, a % b
            return a
        
        gcd_length = gcd(len(str1), len(str2))
        return str1[:gcd_length]

Complexity

⏰ Time complexity: O(n + m + gcd(n, m)), where n and m are the lengths of str1 and str2 respectively. This accounts for computing the GCD and verifying the constructed substring.
🧺 Space complexity: O(gcd(n, m)), for storing the resulting substring.

Problem#

Examples#

Solution#

Method 1 - Run the gcd#

Code#

Complexity#