LeetCode #1071. Greatest Common Divisor of Strings

Time Complexity O(m+n)

Space Complexity O(m+n)

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        // Quick check: if str1 + str2 != str2 + str1, no common divisor exists
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }

        // Find GCD of the lengths
        int gcdLength = gcd(str1.length(), str2.length());

        // Return the prefix of length gcdLength
        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;
    }
}