Watch 10 video solutions for Greatest Common Divisor of Strings, a easy level problem involving Math, String. This walkthrough by NeetCodeIO has 95,797 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
For two strings s and t, we say "t divides s" if and only if s = t + t + t + ... + t + t (i.e., t is concatenated with itself one or more times).
Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.
Example 1:
Input: str1 = "ABCABC", str2 = "ABC" Output: "ABC"
Example 2:
Input: str1 = "ABABAB", str2 = "ABAB" Output: "AB"
Example 3:
Input: str1 = "LEET", str2 = "CODE" Output: ""
Constraints:
1 <= str1.length, str2.length <= 1000str1 and str2 consist of English uppercase letters.Problem Overview: Given two strings str1 and str2, find the largest string that can be repeated multiple times to form both strings. The result must divide both strings exactly, similar to how a numeric GCD divides two numbers.
Approach 1: Iterative Check for Substring Divisors (O((n+m) * min(n,m)) time, O(n) space)
This approach treats the problem literally: try every possible substring that could divide both strings. Start with candidate lengths that divide both len(str1) and len(str2). For each candidate substring from str1, repeatedly concatenate it until it matches the length of both strings, then compare with str1 and str2. If both match, that substring is a valid divisor. This method is straightforward and useful when you want to reason about the divisibility property directly, but it may check many candidates in the worst case.
Because each candidate may require rebuilding strings for verification, the total cost can reach O((n+m) * min(n,m)) time. The space usage is O(n) due to temporary string construction. This solution mainly relies on operations from string manipulation and basic iteration.
Approach 2: Using GCD of Lengths (O(n+m) time, O(1) space)
The optimal insight comes from observing a mathematical property. If a string X divides both str1 and str2, then concatenating the strings in different orders should produce the same result: str1 + str2 == str2 + str1. If this condition fails, no common divisor string exists.
Once that condition holds, the length of the answer must be the greatest common divisor of the two lengths. Compute gcd(len(str1), len(str2)) using the Euclidean algorithm from math. The prefix of length gcd from either string becomes the answer because it repeats to build both strings.
This works because repeating patterns must align perfectly across both strings. The concatenation check validates that they share the same repeating base pattern, and the numeric GCD finds the largest valid repetition block. The algorithm scans the strings once for the concatenation comparison, giving O(n+m) time and constant space.
Recommended for interviews: The GCD-of-lengths approach is what most interviewers expect. It shows you recognized the mathematical structure behind the strings rather than brute forcing substring candidates. Mentioning the concatenation property plus the gcd(len1, len2) observation demonstrates strong pattern recognition across string processing and math concepts.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Check for Substring Divisors | O((n+m) * min(n,m)) | O(n) | When exploring the divisibility concept directly or validating substring patterns step by step |
| GCD of Lengths | O(n+m) | O(1) | Best general solution; optimal for interviews and large strings |