Easy
Greatest Common Divisor of Strings
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 = "SC", str2 = "SU" Output: ""
Constraints
1 <= str1.length, str2.length <= 1000 str1 and str2 consist of English uppercase letters.
We can iterate through both strings using (i) up until the minimum length of both strings. If the lengths of str1 and str2 are divisible by (i), that could be a possible match. Check if the substring of either string can be concatenated to create str1 and str2, if so, return the substring early. However, there is a solution that requires no loops or recursion, and uses the rules of GCD to quickly provide an answer.
*hover to un-blur*
# Iterative solution class Solution: def gcdOfStrings(self, str1: str, str2: str) -> str: # iterate through both strings (i) up untill the minimum len for both strings # if the lengths of both strings are divisible by (i) # check if they both add up to both substrings len1 = len(str1) len2 = len(str2) minimum = min(len2, len2) for i in range(minimum, 0, -1): if len1 % i == 0 and len2 % i == 0: string = str1[:i] concatStr1 = string * (len1 // i) concatStr2 = string * (len2 // i) if concatStr1 == str1 and concatStr2 == str2: return string return "" # Advanced and Elegant solution - Leetcode Editorial class Solution: def gcdOfStrings(self, str1: str, str2: str) -> str: # mathematical GCD approach if str1 + str2 != str2 + str1: return "" maxGCDLength = gcd(len(str1), len(str2)) return str2[:maxGCDLength]