Greatest Common Divisor of Strings

NeetCode: Greatest Common Divisor of Strings · LeetCode: 1071. Greatest Common Divisor of Strings · Difficulty: Easy

A string t divides a string s if s is t repeated one or more times. Given str1 and str2, return the largest string x that divides both, or the empty string if there is none.

Example

Text

Input:  str1 = "ABCABC", str2 = "ABC"    Output: "ABC"
Input:  str1 = "ABABAB", str2 = "ABAB"    Output: "AB"
Input:  str1 = "LEET",   str2 = "CODE"    Output: ""

Brute force: try every prefix length

A common divisor must be a prefix of str1, and its length must divide both lengths. Try prefix lengths from the longest possible (the shorter string's length) down to 1, and return the first prefix that, repeated, rebuilds both strings. String.repeat(count) returns the string repeated count times.

Java

class Solution {
    private boolean divides(String t, String s) {
        return !t.isEmpty() && s.length() % t.length() == 0
                && t.repeat(s.length() / t.length()).equals(s);
    }

    public String gcdOfStrings(String str1, String str2) {
        int max = Math.min(str1.length(), str2.length());
        for (int len = max; len >= 1; len--) {
            String cand = str1.substring(0, len);
            if (divides(cand, str1) && divides(cand, str2)) {
                return cand;
            }
        }
        return "";
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println("[" + s.gcdOfStrings("ABCABC", "ABC") + "]");
        System.out.println("[" + s.gcdOfStrings("ABABAB", "ABAB") + "]");
        System.out.println("[" + s.gcdOfStrings("LEET", "CODE") + "]");
    }
}

Output

[ABC]
[AB]
[]

Time: O(min(m, n) * (m + n)) for lengths m and n: up to min(m, n) candidates, each costing a linear build and compare. Space: O(m + n).

Optimal: concatenation check, then gcd of the lengths

If a common divisor exists, then str1 + str2 equals str2 + str1, because both are repetitions of the same block. Conversely, if the two concatenations differ, no common block exists and the answer is empty. When they are equal, the answer is the prefix whose length is gcd(len1, len2): the block length must divide both lengths, and the gcd is the largest such number.

For ABABAB and ABAB: both concatenations are ABABABABAB, and gcd(6, 4) = 2, so the answer is the first two letters, AB.

Java

class Solution {
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public String gcdOfStrings(String str1, String str2) {
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }
        return str1.substring(0, gcd(str1.length(), str2.length()));
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println("[" + s.gcdOfStrings("ABCABC", "ABC") + "]");
        System.out.println("[" + s.gcdOfStrings("ABABAB", "ABAB") + "]");
        System.out.println("[" + s.gcdOfStrings("LEET", "CODE") + "]");
    }
}

Output

[ABC]
[AB]
[]

Time: O(m + n) (the gcd takes O(log min(m, n))). Space: O(m + n) for the concatenations.

The block length gcd(len1, len2) never exceeds str1.length(), so substring is always in range. Both strings are non-empty by the constraints.