Code Implementation

from math import gcd

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # If concatenating in both orders gives different results, no common divisor exists
        if str1 + str2 != str2 + str1:
            return ""
        # The GCD of the lengths gives the length of the common substring
        length = gcd(len(str1), len(str2))
        return str1[:length]
      

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if (str1 + str2 != str2 + str1) return "";
        int len = gcd(str1.size(), str2.size());
        return str1.substr(0, len);
    }
private:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};
      

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if (!(str1 + str2).equals(str2 + str1)) return "";
        int len = gcd(str1.length(), str2.length());
        return str1.substring(0, len);
    }
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
      

var gcdOfStrings = function(str1, str2) {
    if (str1 + str2 !== str2 + str1) return "";
    const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
    let len = gcd(str1.length, str2.length);
    return str1.slice(0, len);
};
      

Problem Description

Given two strings, str1 and str2, you need to find the greatest common divisor (GCD) string that can divide both strings. A string X is said to divide string S if S can be formed by concatenating one or more copies of X.

Your task is to return the largest string X such that X divides both str1 and str2. If there is no such string, return an empty string "".

Key Constraints:

• Both input strings are non-empty and consist only of uppercase English letters.
• You must return only one valid solution (the largest possible).

Thought Process

To solve this problem, we first need to understand what it means for one string to "divide" another. If string X divides string S, then S must be a sequence of repeated X substrings. For example, "AB" divides "ABAB" because "ABAB" = "AB" + "AB".

A brute-force solution would be to try all possible substrings of str1 or str2 and check if each divides both. However, this would be inefficient, especially for longer strings.

Instead, we can look for patterns and mathematical properties. The key realization is that if a common divisor string exists, it must be a prefix of both strings, and the length of this substring must divide the lengths of both str1 and str2. This naturally leads to considering the greatest common divisor (GCD) of the lengths.

We also notice that if str1 + str2 is not equal to str2 + str1, then there is no common divisor string, since the order of concatenation would produce different results.

Solution Approach

• Step 1: Check for Concatenation Consistency
  If str1 + str2 is not equal to str2 + str1, then there is no string that can divide both strings. This is because the repeating pattern is not consistent between the two strings.
• Step 2: Find the GCD of the Lengths
  If a common divisor string exists, its length must be the greatest common divisor (GCD) of the lengths of str1 and str2. This is because only a substring of that length can evenly divide both strings.
• Step 3: Extract and Return the GCD String
  Take the prefix of str1 (or str2, since they're equivalent up to this point) with length equal to the GCD found in the previous step. This substring is the answer.

This approach is efficient because it avoids unnecessary substring checks and leverages mathematical properties for a direct solution.

Example Walkthrough

Example:
str1 = "ABCABC", str2 = "ABC"

1. Check concatenation:
   "ABCABC" + "ABC" = "ABCABCABC"
   "ABC" + "ABCABC" = "ABCABCABC"
   Since both are equal, continue.
2. Find GCD of lengths:
   Length of "ABCABC" = 6
   Length of "ABC" = 3
   GCD(6, 3) = 3
3. Extract prefix of length 3:
   "ABCABC"[:3] = "ABC"
4. Check if "ABC" divides both strings:
   "ABCABC" = "ABC" + "ABC"
   "ABC" = "ABC"
   Both are divisible by "ABC".
5. Return "ABC" as the answer.

Time and Space Complexity

• Brute-force approach:
  Try all possible prefixes and check if they divide both strings. This could take up to O(N * M) time, where N and M are the lengths of the strings, since each check could take O(N + M) time.
• Optimized approach (current solution):
  
  • Calculating the GCD of two numbers is O(log(min(N, M))).
  • Concatenation and comparison of the two strings is O(N + M).
  • Extracting the substring is O(1) (since it's just a slice).
  Total time complexity: O(N + M)
  Space complexity: O(N + M) for concatenated string comparisons, otherwise O(1) extra space.

Summary

The problem asks for the largest string that can evenly divide two given strings. By recognizing the relationship between string repetition and the mathematical GCD, we avoid brute-force checks and arrive at an elegant, efficient solution. The key insight is that if a GCD string exists, it must be a prefix whose length divides both original strings, and the concatenation order must be consistent. This approach is both concise and optimal for the problem.