1000 - 1099
1071 - Greatest Common Divisor of Strings (Easy)
Problem Link
https://leetcode.com/problems/greatest-common-divisor-of-strings/
Problem Statement
For two strings s and t, we say "t divides s" if and only if s = t + ... + t (i.e., t is concatenated with itself one or more times).
Given two strings str1 and str2, return the largest stringxsuch thatxdivides bothstr1andstr2.
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 1: Optimal Solution - String equals with GCD
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
# if str1 + str2 == str2 + str1 is true, that means they have the same divisor
# see example 1: "ABCABC" + "ABC" = "ABC" + "ABCABC"
# if there is no such divisor, then return ""
# otherwise, we can use gcd to find the lengths
# the answer is either
# - str1[0 .. g] or
# - str2[0 .. g]
# where g is the gcd of their length
return "" if str1 + str2 != str2 + str1 else str1[:gcd(len(str1), len(str2))]Approach 2: Substring Division
As stated in the problem, t divides s which means length of t is either equal or factor of t & s.
First, iterate over the smallest string min(t, s), use the index to substring(0, index) and divide both s & t and if there's no reminder then apply factor (no. of times) with str1 and str2 to find string equals.
class Solution {
/**
* m - Str1, n - str2
*
* Time complexity - O(min(m, n) * (m + n))
* Space complexity - O(1)
*/
public String gcdOfStrings(String str1, String str2) {
int str1Len = str1.length(), str2Len = str2.length();
// Check 1st char in both strings
if (str1.charAt(0) != str2.charAt(0)) {
return "";
}
// Function - Check both strings are factor by divisor substring length
Function<Integer, Boolean> isDivisor = len -> {
if (str1Len % len != 0 || str2Len % len != 0) {
return false;
}
int f1 = str1Len / len, f2 = str2Len / len;
String mini = str2.substring(0, len);
return Objects.equals(mini.repeat(f1), str1) && Objects.equals(mini.repeat(f2), str2);
};
for (int i = Math.min(str1Len, str2Len); i > 0; i--) {
if (isDivisor.apply(i)) {
return str1.substring(0, i);
}
}
return "";
}
}