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.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.
Java
Time Complexity: O(N), where N is the sum of lengths of str1 and str2 due to equality check.
Space Complexity: O(1).
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.
JavaScript
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 | 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. |
Greatest Common Divisor of Strings - Leetcode 1071 - Python • NeetCodeIO • 76,336 views views
Watch 9 more video solutions →Practice Greatest Common Divisor of Strings with our built-in code editor and test cases.
Practice on FleetCode