Skip to main content

1071 - Greatest Common Divisor of Strings (Easy)

https://leetcode.com/problems/greatest-common-divisor-of-strings/

Problem Statement​

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 stringxsuch thatxdivides bothstr1andstr2.

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.

Approach 1: Optimal Solution - String equals with GCD​

Written by @wingkwong
class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # if str1 + str2 == str2 + str1 is true, that means they have the same divisor
        # see example 1: "ABCABC" + "ABC" = "ABC" + "ABCABC"
        # if there is no such divisor, then return ""
        # otherwise, we can use gcd to find the lengths
        # the answer is either 
        # - str1[0 .. g] or 
        # - str2[0 .. g]
        # where g is the gcd of their length
        return "" if str1 + str2 != str2 + str1 else str1[:gcd(len(str1), len(str2))]

Approach 2: Substring Division​

As stated in the problem, t divides s which means length of t is either equal or factor of t & s.

First, iterate over the smallest string min(t, s), use the index to substring(0, index) and divide both s & t and if there's no reminder then apply factor (no. of times) with str1 and str2 to find string equals.

Written by @vigneshshiv
class Solution {

    /**
     * m - Str1, n - str2
     * 
     * Time complexity - O(min(m, n) * (m + n))
     * Space complexity - O(1)
     */
    public String gcdOfStrings(String str1, String str2) {
        int str1Len = str1.length(), str2Len = str2.length();
        // Check 1st char in both strings
        if (str1.charAt(0) != str2.charAt(0)) {
            return "";
        }
        // Function - Check both strings are factor by divisor substring length
        Function<Integer, Boolean> isDivisor = len -> {
            if (str1Len % len != 0 || str2Len % len != 0) {
                return false;
            }
            int f1 = str1Len / len, f2 = str2Len / len;
            String mini = str2.substring(0, len);
            return Objects.equals(mini.repeat(f1), str1) && Objects.equals(mini.repeat(f2), str2);
        };
        for (int i = Math.min(str1Len, str2Len); i > 0; i--) {
            if (isDivisor.apply(i)) {
                return str1.substring(0, i);
            }
        }
        return "";
    }
}