1071. Greatest Common Divisor of Strings - Detailed Explanation

Problem Statement

You are given two strings, str1 and str2. A string x is said to divide another string s if s can be formed by concatenating x one or more times. In other words, there exists an integer n ≥ 1 such that:

s = x repeated n times

The goal is to find the largest string x (in terms of length) that divides both str1 and str2. If there is no such string, return an empty string "".

Examples:

1. Example 1:

   • Input: str1 = "ABCABC", str2 = "ABC"
   • Output: "ABC"
   • Explanation:
     "ABC" divides "ABCABC" (it can be repeated twice) and also divides "ABC" (repeated once).

2. Example 2:

   • Input: str1 = "ABABAB", str2 = "ABAB"
   • Output: "AB"
   • Explanation:
     "AB" divides "ABABAB" (repeated 3 times) and "ABAB" (repeated 2 times). Note that even though "ABAB" divides "ABAB", it does not divide "ABABAB".

3. Example 3:

   • Input: str1 = "LEET", str2 = "CODE"
   • Output: ""
   • Explanation:
     There is no non-empty string that can be repeatedly concatenated to form both "LEET" and "CODE".

Constraints:

• Both str1 and str2 consist of uppercase English letters.
• The lengths of the strings are between 1 and 1000.

Hints

• Divisibility Property:
  If a string x divides both str1 and str2, then it must be a prefix of both strings.

• Concatenation Check:
  A useful insight is that if x divides both str1 and str2, then the concatenation str1 + str2 must equal str2 + str1. If this property does not hold, there is no common divisor string.

• GCD of Lengths:
  The maximum possible length of the common divisor string is the greatest common divisor (GCD) of the lengths of str1 and str2. Once you compute this value, the candidate string is simply the prefix of str1 (or str2) with that length.

Approaches

Approach 1: Mathematical (Using GCD)

1. Concatenation Check:
   First, check whether str1 + str2 is equal to str2 + str1. If they are not equal, no string x can form both str1 and str2 by repeated concatenation, so return "".

2. Compute GCD of Lengths:
   If the above check passes, compute the greatest common divisor (gcd) of the lengths of str1 and str2. Let this value be g.

3. Extract and Return the Divisor:
   The answer is the first g characters of str1. This substring, when repeated the necessary number of times, can reconstruct both str1 and str2.

Approach 2: Brute Force (Not Recommended)

• Enumerate Divisors:
  Generate all possible prefixes of str1 that are divisors (i.e., whose length divides the length of str1), and check whether they also divide str2.
• Drawback:
  This approach is less efficient and more cumbersome compared to the mathematical method.

Step-by-Step Walkthrough (Mathematical Approach)

Let’s walk through an example:

Example:
str1 = "ABABAB", str2 = "ABAB"

1. Check Concatenation Property:

   • str1 + str2 gives "ABABABABAB".
   • str2 + str1 gives "ABABABABAB".
     Since both are equal, a common divisor string might exist.

2. Compute the GCD of Lengths:

   • len(str1) = 6
   • len(str2) = 4
   • The greatest common divisor of 6 and 4 is 2.

3. Extract the Prefix:

   • The candidate divisor string is the first 2 characters of str1, which is "AB".

4. Verification:

   • Check that "AB" repeated 3 times equals "ABABAB" and repeated 2 times equals "ABAB".
     This confirms that "AB" is the greatest common divisor string.