Greatest Common Divisor of Strings

Problem Description

For two strings s and t, we say “t divides s” if and only if s = t + t + 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

Constraints

• 1 ≤ str1.length, str2.length ≤ 1000
• str1 and str2 consist of English uppercase letters.

Math Logic: Concatenation and Length GCD

If two strings str1 and str2 have a common divisor string x, then concatenating them in different orders must produce the same result: str1 + str2 == str2 + str1. If this condition is not met, a common divisor string does not exist, and we return "".

If they do commute, the length of the greatest common divisor string must be the greatest common divisor (GCD) of the lengths of str1 and str2. We compute gcd(len(str1), len(str2)) and return the prefix of str1 of that length.

Solution: Commuting Check + GCD Length

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        // Check if a common divisor string is possible
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }

        // Length of the GCD string is the GCD of the two lengths
        int gcdLength = gcd(str1.length(), str2.length());
        return str1.substring(0, gcdLength);
    }

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

import math

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # Check if a common divisor string is possible
        if str1 + str2 != str2 + str1:
            return ""

        # Length of the GCD string is the GCD of the two lengths
        gcd_length = math.gcd(len(str1), len(str2))
        return str1[:gcd_length]

#include <string>
#include <numeric>

class Solution {
public:
    std::string gcdOfStrings(std::string str1, std::string str2) {
        if (str1 + str2 != str2 + str1) {
            return "";
        }

        int gcdLength = std::gcd(str1.length(), str2.length());
        return str1.substr(0, gcdLength);
    }
};

Complexity Analysis:

• Time Complexity: O(N + M) where N and M are the lengths of str1 and str2. The concatenation check takes linear time. The GCD calculation is logarithmic.
• Space Complexity: O(N + M) to create the concatenated strings for comparison.

← All Problems