Problem Description

This problem asks you to find the greatest common divisor (GCD) of two strings. A string t "divides" a string s if s can be formed by concatenating t with itself one or more times. For example, "abc" divides "abcabcabc" because "abcabcabc" = "abc" + "abc" + "abc".

Given two strings str1 and str2, you need to find the largest string x that divides both strings. If no such string exists, return an empty string.

The solution works by checking all possible prefix lengths from the longest to the shortest. For each prefix length i, it takes the first i characters from str1 as a candidate string t. It then verifies if this candidate can divide both str1 and str2 using the helper function check(). The check() function concatenates the candidate string repeatedly until it reaches or exceeds the target string's length, then compares if they match exactly.

The algorithm starts with the maximum possible length (the minimum of the two string lengths) and works downward, returning the first valid divisor found. This ensures the result is the largest possible common divisor string.

For example:

• If str1 = "ABCABC" and str2 = "ABC", the result would be "ABC"
• If str1 = "ABABAB" and str2 = "ABAB", the result would be "AB"
• If str1 = "LEET" and str2 = "CODE", the result would be "" (empty string)

Intuition

The key insight is that if a string x divides both str1 and str2, then x must be a prefix of both strings. Why? Because when we start building str1 or str2 by repeating x, the first copy of x will form the beginning of the string.

Since we want the largest possible x, we should check longer prefixes first. The maximum possible length of x is min(len(str1), len(str2)) because x must fit at least once into both strings.

The approach becomes clear: try every possible prefix length starting from the longest and working our way down. For each candidate prefix, we need to verify two things:

1. Can this prefix, when repeated, reconstruct str1 exactly?
2. Can this same prefix, when repeated, reconstruct str2 exactly?

The first prefix that satisfies both conditions is our answer. We check from longest to shortest because we want the greatest common divisor string, not just any common divisor.

The verification step is straightforward - we keep concatenating the candidate string to itself until we reach the target length. If the result matches the original string exactly, then the candidate divides the string. If we've checked all possible prefixes and none work, then no common divisor exists, so we return an empty string.

This greedy approach guarantees we find the optimal solution because we're systematically checking all possibilities in order of preference (longest first).

Learn more about Math patterns.

Solution Approach

The implementation uses a brute-force approach with a helper function to verify if a candidate string divides the target strings.

Helper Function check(a, b):

• Takes two parameters: a (the candidate divisor) and b (the string to check)
• Builds a string c by repeatedly concatenating a to itself
• Continues concatenation while len(c) < len(b)
• Returns True if the constructed string c equals b, otherwise False

Main Algorithm:

1. Iterate through possible lengths: Use a loop from min(len(str1), len(str2)) down to 1

   • We start from the maximum possible length because we want the largest divisor
   • The range goes from largest to smallest: range(min(len(str1), len(str2)), 0, -1)

2. Extract candidate prefix: For each length i, extract the prefix t = str1[:i]

   • This gives us a candidate string that might divide both inputs

3. Verify the candidate: Check if t divides both str1 and str2

   • Call check(t, str1) to verify if t divides str1
   • Call check(t, str2) to verify if t divides str2
   • Both conditions must be True for t to be a valid answer

4. Return the result:

   • If both checks pass, immediately return t (this is the largest valid divisor)
   • If no valid divisor is found after checking all possibilities, return an empty string ''

Time Complexity: O(n * (m + n)) where n = len(str1) and m = len(str2). We check at most min(m, n) prefixes, and for each prefix, the check function takes O(m + n) time.

Space Complexity: O(max(m, n)) for the temporary string c created in the check function.

Example Walkthrough

Let's walk through the algorithm with str1 = "ABABAB" and str2 = "ABAB".

Step 1: Determine the range of possible prefix lengths

• len(str1) = 6, len(str2) = 4
• Maximum possible length = min(6, 4) = 4
• We'll check prefix lengths: 4, 3, 2, 1 (in that order)

Step 2: Check prefix length 4

• Candidate: t = str1[:4] = "ABAB"
• Check if "ABAB" divides "ABABAB":
  • Build: "ABAB" → length 4 < 6, continue
  • Build: "ABAB" + "ABAB" = "ABABABAB" → length 8 ≥ 6, stop
  • Compare: "ABABABAB" ≠ "ABABAB" ✗
• Since the first check fails, skip checking str2

Step 3: Check prefix length 3

• Candidate: t = str1[:3] = "ABA"
• Check if "ABA" divides "ABABAB":
  • Build: "ABA" → length 3 < 6, continue
  • Build: "ABA" + "ABA" = "ABAABA" → length 6 ≥ 6, stop
  • Compare: "ABAABA" ≠ "ABABAB" ✗
• First check fails, move on

Step 4: Check prefix length 2

• Candidate: t = str1[:2] = "AB"
• Check if "AB" divides "ABABAB":
  • Build: "AB" → length 2 < 6, continue
  • Build: "AB" + "AB" = "ABAB" → length 4 < 6, continue
  • Build: "ABAB" + "AB" = "ABABAB" → length 6 ≥ 6, stop
  • Compare: "ABABAB" = "ABABAB" ✓
• Check if "AB" divides "ABAB":
  • Build: "AB" → length 2 < 4, continue
  • Build: "AB" + "AB" = "ABAB" → length 4 ≥ 4, stop
  • Compare: "ABAB" = "ABAB" ✓
• Both checks pass! Return "AB"

Result: The greatest common divisor string is "AB"

Solution Implementation

Time and Space Complexity

Time Complexity: O(min(m, n) * (m + n)) where m = len(str1) and n = len(str2)

• The outer loop runs from min(len(str1), len(str2)) down to 1, which is O(min(m, n)) iterations
• For each iteration i, we create a substring t = str1[:i] which takes O(i) time
• The check function is called twice for each iteration:
  • check(t, str1): The while loop builds string c by concatenating t until len(c) >= len(str1). This performs approximately len(str1)/len(t) concatenations, and each concatenation creates a new string. The total time is O(m) for building the string plus O(m) for the final comparison
  • check(t, str2): Similarly, this takes O(n) time
• Therefore, each iteration takes O(m + n) time
• Total time complexity: O(min(m, n) * (m + n))

Space Complexity: O(max(m, n))

• The substring t can be at most O(min(m, n)) in size
• Inside the check function, string c is built up to the size of the longer input string, which requires O(max(m, n)) space
• The space is dominated by the string c in the check function
• Total space complexity: O(max(m, n))

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Checking Divisibility Constraint

A critical pitfall is assuming any common substring that appears in both strings is a valid divisor. The candidate must divide both strings exactly - meaning the string length must be divisible by the candidate length.

Problematic approach:

# This would fail because it doesn't check if lengths are divisible
for length in range(min(len(str1), len(str2)), 0, -1):
    candidate = str1[:length]
    if can_construct(candidate, str1) and can_construct(candidate, str2):
        return candidate

Solution: Add a divisibility check before the expensive string construction:

for length in range(min(len(str1), len(str2)), 0, -1):
    # Check if this length can divide both strings
    if len(str1) % length != 0 or len(str2) % length != 0:
        continue
  
    candidate = str1[:length]
    if can_construct(candidate, str1) and can_construct(candidate, str2):
        return candidate

2. Inefficient String Construction in Helper Function

Building strings through repeated concatenation in a loop is inefficient and can cause performance issues for large inputs.

Problematic approach:

def can_construct(pattern: str, target: str) -> bool:
    constructed = ""
    while len(constructed) < len(target):
        constructed += pattern  # String concatenation creates new object each time
    return constructed == target

Solution: Use multiplication operator or calculate repetitions directly:

def can_construct(pattern: str, target: str) -> bool:
    if len(target) % len(pattern) != 0:
        return False
  
    repetitions = len(target) // len(pattern)
    return pattern * repetitions == target

3. Missing Early Termination Check

A mathematical property of GCD strings is that if str1 + str2 != str2 + str1, then no common divisor exists. Not checking this upfront wastes computation time.

Solution: Add an early termination check:

def gcdOfStrings(self, str1: str, str2: str) -> str:
    # Early termination: if concatenation order matters, no GCD exists
    if str1 + str2 != str2 + str1:
        return ""
  
    # Continue with the regular algorithm...

4. Not Leveraging Mathematical GCD Property

The length of the GCD string must be the GCD of the two string lengths. Not using this property leads to checking many impossible candidates.

Optimal approach using math.gcd:

import math

def gcdOfStrings(self, str1: str, str2: str) -> str:
    if str1 + str2 != str2 + str1:
        return ""
  
    # The GCD string length must be gcd(len(str1), len(str2))
    gcd_length = math.gcd(len(str1), len(str2))
    return str1[:gcd_length]

This reduces the time complexity from O(n * (m + n)) to O(m + n) where m and n are the string lengths.