Greatest Common Divisor of Strings - Solution & Explanation
Problem Statement
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 <= 1000str1andstr2consist of English uppercase letters.
Approach Overview
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 1: Using GCD of Lengths
This approach leverages the mathematical concept of the Greatest Common Divisor (GCD) to determine the largest string that divides both given strings, str1 and str2.
First, check if str1 + str2 == str2 + str1. If not, that means there's no possible common divisor string. If they are equal, find the GCD of the lengths of the two strings. The prefix of this length is the required greatest common divisor string.
The function gcd_of_strings checks if str1 + str2 is equal to str2 + str1. If not, they don't have a common divisor string. If they do, it calculates the GCD of the lengths of the two strings and uses this GCD to slice the first string to obtain the longest common divisor string.
Complexity
Time Complexity: O(N), where N is the sum of lengths of str1 and str2 due to equality check.
Space Complexity: O(1).
Approach 2: Iterative Check for Substring Divisors
In this method, the idea is to iterate over possible substring lengths of the two input strings and check if these substrings can divide both strings. We start with the longest possible potential divisor, reducing the length until a valid divisor is found.
This is less efficient but straightforward when debugging or understanding the repetitive nature of string divisibility.
The C# solution tries all possible lengths starting from the smallest length of the given strings down to 1. For each possible divisor length, it checks if it evenly divides both strings, and then verifies if replacing that substring from both strings results in empty strings, confirming it as a valid divisor.
Code
C#
JavaScript
Complexity
Time Complexity: O(N * M), where N and M are the lengths of str1 and str2.
Space Complexity: O(N + M) for storing temporary strings.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Using GCD of Lengths | Time Complexity: O(N), where N is the sum of lengths of str1 and str2 due to equality check. |
| Iterative Check for Substring Divisors | Time Complexity: O(N * M), where N and M are the lengths of str1 and str2. |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Greatest Common Divisor of Strings - Leetcode 1071 - Python • NeetCodeIO • 99,892 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Greatest Common Divisor of Strings easy or hard?
How to solve Greatest Common Divisor of Strings in O(n)?
Greatest Common Divisor of Strings Python or Java solution
What is the best approach for Greatest Common Divisor of Strings?
Is Greatest Common Divisor of Strings asked at Google Amazon Meta?
What data structure is used in Greatest Common Divisor of Strings?
What is the time complexity of Greatest Common Divisor of Strings?
Ready to solve this problem?
Practice Greatest Common Divisor of Strings with our built-in code editor and test cases.
Practice on FleetCode