Please see github.com/anusha-murali for all of my repositories.
This is a beautiful problem from LeetCode (Problem #1071).
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: ""
Solution
We note that if there is a non-empty GCD of str1
and str
, then it must be that str1 + str2 == str2 + str1
.
If str1 + str2 == str2 + str1
, then we want to return the slice of the length of GCD of either string. Hence, our code is as follows:
def gcdOfStrings(str1, str2):
if str1 + str2 == str2 + str1:
return str1[:math.gcd(len(str1), len(str2))]
else:
return ""
Runtime:
Back to String and Array Problems