1071. Greatest Common Divisor of Strings

Description of 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.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

1 <= str1.length, str2.length <= 1000
str1 and str2 consist of English uppercase letters.

Solution 1

Tags:

Explanation

This is the official answer.

By definition, A string s is divisble if there is string t such that s = t + t + t + ... + t.

Consider divisble two strings s1 and s2:

Assume the common string t exists (i.e. s1 = t^m, s2 = t^n), the greatest common string is t^gcd(m,n).
If they are non-divisble string or there is no common string, then s1 + s2 != s2 + s1.

Code (Rust)

impl Solution {
    pub fn gcd_of_strings(str1: String, str2: String) -> String {
        if [&str1[..], &str2[..]].join("") != [&str2[..], &str1[..]].join("") {
            return "".to_string();
        }

        let mut m = str1.len();
        let mut n = str2.len();

        if m < n {
            let temp = m;
            m = n;
            n = temp;
        }

        while n > 0 {
            let temp = m;
            m = n;
            n = temp % n;
        }

        return String::from(&str1[..m]);
    }
}

Complexity

Time Complexity

\( T(n) = O( (m+n) + \log(m \cdot n) ) = O( m+n ) \)
- Creates str1 + str2 and str2 + str1 for comparsion
- Use Euclid's algorithm

Auxiliary Space

\(S(n) = O(2(m+n)) = O(m+n)\)
- Creates str1 + str2 and str2 + str1 for comparsion

Leetbook