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:

  1. Check Divisibility:
    • We need to check if a substring x can repeatedly form both str1 and str2.
  2. 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.
  3. 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.