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.

This question sits in the array and string group, which coding interview courses teach under the two pointers pattern, where two indices move through one or two sequences in a single pass. Here a number theory identity replaces the scan, so the solution is shorter than a pointer walk. The recurring LeetCode patterns post lists this group alongside the other techniques worth recognizing quickly.

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 of 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 the GCD of the lengths: If the check above passes, compute the greatest common divisor of the lengths of str1 and str2. Call this value g.

3. Extract and return the divisor: The answer is the first g characters of str1. Repeated the right number of times, this substring reconstructs both str1 and str2.

Approach 2: brute force (not recommended)

• Enumerate divisors: Generate every prefix of str1 whose length divides the length of str1, then check whether each one also divides str2.
• Drawback: This approach is correct, and it is slower and more awkward to write than the mathematical method.

Step-by-step walkthrough (mathematical approach)

Let us walk through an example:

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

1. Check the 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 the 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.