Greatest Common Divisor of Strings solution and explanation
Google
9 more videos on this problem
Greatest Common Divisor of Strings - Leetcode 1071 - PythonNeetCodeIO · 9:16 · 99K views
Greatest Common Divisor of Strings | Leetcode - 1071Algorithms Made Easy · 8:11 · 26K views
Leetcode | 1071. Greatest Common Divisor of Strings | Easy | Java SolutionDeveloper Docs · 4:09 · 7K views
Greatest Common Divisor of Strings LeetCode 1071 - Intuitive Guide + CodeCodingNinja · 10:27 · 6K views
1071. Greatest Common Divisor of Strings | LeetCode 75 #2 | Array / StringShaheer Keerirakath · 1:34 · 6K views
Greatest Common Divisor of Strings - LeetCode 1071 #leetcode #leetcode75Deepti Talesra · 8:23 · 6K views
1071. Greatest Common Divisor of Strings (Leetcode Easy)Programming Live with Larry · 13:25 · 4K views
Greatest Common Divisor of Strings| 1071 Leetcode |C++| Easiest Explanation |Line by Line Code | DSADSA Buddy · 5:34 · 4K views
Leetcode 1071 Greatest Common Divisor of Strings (Java)TheAnalyticGuy · 5:09 · 3K views
LeetCode 1071 Greatest Common Divisor of StringsJeevan Kumar - Cracckify · 2:39 · 2K views
The problem
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.
def gcd_of_strings(str1, str2):
def gcd(a, b):
while b:
a, b = b, a % b
return a
if str1 + str2 != str2 + str1:
return ""
length = gcd(len(str1), len(str2))
return str1[:length]class Solution {
public String gcdOfStrings(String str1, String str2) {
if (!(str1 + str2).equals(str2 + str1)) {
return "";
}
return str1.substring(0, gcd(str1.length(), str2.length()));
}
private int gcd(int a, int b) {
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
}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.
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.
function gcdOfStrings(str1, str2) {
var isDivisible = function(s, x) {
return s.split(x).join('') === '';
};
for (let i = Math.min(str1.length, str2.length); i > 0; i--) {
if (str1.length % i === 0 && str2.length % i === 0) {
let candidate = str1.substring(0, i);
if (isDivisible(str1, candidate) && isDivisible(str2, candidate)) {
return candidate;
}
}
}
return '';
}public class Solution {
public string GcdOfStrings(string str1, string str2) {
int minLength = Math.Min(str1.Length, str2.Length);
for (int i = minLength; i > 0; i--) {
if (str1.Length % i == 0 && str2.Length % i == 0) {
string candidate = str1.Substring(0, i);
if (str1.Replace(candidate, "") == "" && str2.Replace(candidate, "") == "") {
return candidate;
}
}
}
return "";
}
}In the JavaScript solution, we define a helper function isDivisible to check if a candidate string can evenly divide a given string. We then iterate over potential lengths starting with the shorter length downwards, checking for each whether it can serve as a valid divisor for both strings.
Time Complexity: O(N * M), N and M being the lengths of str1 and str2.
Space Complexity: O(N + M).
Approach 3: Default Approach
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
if (str1 + str2 != str2 + str1) return "";
int n = __gcd(str1.size(), str2.size());
return str1.substr(0, n);
}
};func gcdOfStrings(str1 string, str2 string) string {
if str1+str2 != str2+str1 {
return ""
}
n := gcd(len(str1), len(str2))
return str1[:n]
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}impl Solution {
pub fn gcd_of_strings(str1: String, str2: String) -> String {
if str1.clone() + &str2 != str2.clone() + &str1 {
return String::from("");
}
fn gcd(a: usize, b: usize) -> usize {
if b == 0 {
return a;
}
gcd(b, a % b)
}
let (m, n) = (str1.len().max(str2.len()), str1.len().min(str2.len()));
str1[..gcd(m, n)].to_string()
}
}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), N and M being the lengths of str1 and str2. |
| Default Approach | – |
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 |
Frequently asked questions
Is Greatest Common Divisor of Strings easy or hard?
The problem is classified as Easy on LeetCode. The main challenge is spotting the mathematical insight that links string repetition with the GCD of lengths. Once that observation is made, the implementation is short and efficient.
How to solve Greatest Common Divisor of Strings in O(n)?
Check if str1 + str2 equals str2 + str1. If they differ, no common divisor string exists. If they match, compute gcd(len(str1), len(str2)) using the Euclidean algorithm and return the prefix of that length from either string. The overall complexity is O(n+m).
Greatest Common Divisor of Strings Python or Java solution
In Python or Java, compute gcd(len(str1), len(str2)) using the built-in math utilities or a Euclidean algorithm implementation. After verifying str1 + str2 equals str2 + str1, return str1.substring(0, gcdLength) or str1[:gcdLength].
What is the best approach for Greatest Common Divisor of Strings?
The most efficient approach uses the GCD of the string lengths. First verify that str1 + str2 equals str2 + str1 to ensure both strings share the same repeating base pattern. Then compute gcd(len(str1), len(str2)) and return the prefix of that length. This runs in O(n+m) time with O(1) extra space.
Is Greatest Common Divisor of Strings asked at Google Amazon Meta?
String pattern and GCD-based reasoning problems appear in interviews at companies like Google, Amazon, and Meta. This problem tests pattern recognition, mathematical reasoning with GCD, and efficient string manipulation.
What data structure is used in Greatest Common Divisor of Strings?
The problem primarily uses string operations and a mathematical GCD calculation. No advanced data structures are required. The key concepts involve string concatenation checks and computing the greatest common divisor of two integers.
What is the time complexity of Greatest Common Divisor of Strings?
The optimal solution runs in O(n+m) time because it compares concatenated strings once and computes the numeric GCD of the lengths. Space complexity is O(1). A brute-force substring checking approach can take up to O((n+m) * min(n,m)) time.