💬 Discord
Sign In
NeetCode #882LC-1071EasyMath & GeometryNC 250
← Back to All Problems

#882 · #1071 · Greatest Common Divisor of Strings(字符串的最大公因子)

📌 Problem Statement & Constraints

For two strings str1 and str2, return the largest string x such that x divides both, meaning both strings are formed by concatenating one or more copies of x. Return an empty string if no such x exists. Constraints: 1 <= str1.length, str2.length <= 1000, both consist of uppercase English letters.

💡 Core Algorithmic Approaches

  1. If a common divisor string exists, then str1 + str2 == str2 + str1 must hold -- this is both necessary and sufficient.
  2. When the condition holds, the answer is the prefix of str1 whose length is gcd(len(str1), len(str2)).
  3. The gcd of the lengths is the largest block size that can tile both strings simultaneously.
  4. If the condition fails, no common divisor exists, so return an empty string.

💻 Benchmark Python3 Implementation

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # a common divisor exists iff the strings commute under concatenation
        if str1 + str2 != str2 + str1:
            return str()
        from math import gcd
        return str1[:gcd(len(str1), len(str2))]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m + n): the concatenation comparison is linear; the gcd is O(log min(m, n)).
💾 Space Complexity
O(m + n) for the two temporary concatenations.

⚠️ Interview Pitfalls & Follow-ups

  • Skipping the commutation test: returning the gcd-length prefix without it can return a prefix that does not actually divide both strings (for example ABABAB and ABAB).
  • Using min(len(str1), len(str2)) instead of the gcd: that length need not divide either string.
  • Forgetting the empty-string case: strings such as ABC and DEF share no divisor and must return an empty string.
  • Testing str1 == str2: the correct check is the concatenation commutation, not string equality.