Greatest Common Divisor of Strings - Leetcode 1071 - Python

Solving Greatest Common Divisor of Strings Leetcode 1071, today's daily leetcode problem on January 31st.

0:00 - Read the problem
1:10 - Drawing Explanation
5:32 - Coding Explanation

leetcode 1071

#neetcode #leetcode #python

[hithambasheir]

I was stuck on this problem and it literally took me the first 3 minutes to understand where I'm blocked, paused the video and successfully solved it 🥳

[girishnakate]

I had asked for more easy problems and here you are. Thank you.

[def__init]

Maybe it’s just late but I feel like I’ve seen easier mediums than this

[Snoresville]

there is an insane solution that involves knowing that there is a GCD of strings if str1 + str2 == str2 + str1

[lamborghinicentenario]

I found this solution that works, unlike the solution in this video (which doesn't seem to solve all test cases on my end):

class Solution(object):
def gcdOfStrings(self, str1, str2):

if str1 + str2 != str2 + str1:
return ""

def gcd(a, b):
while b:
a, b = b, a % b
return a

return str1[:gcd(len(str1), len(str2))]

[lassekock]

Correct me if I'm wrong, but in line 9, minute 8:39 it does not work in bot cases as you described. Behind the "and" (str1[:l] * f1 == str1 and str2[:l] * f2 == str2) we need to compare str2 to the multiple of str1 because otherwise it is not checked if the actual letters of the substring are the same in str1 and str2. So this is the correct way to do it: str1[:l] * f1 == str1 and str1[:l] * f2 == str2

[BRBallin]

That modulo operation to rule out the substring sizing is such a good pointer for optimizing the solution

[PrajaktaKarandikar-tw]

beautiful optimizations for a not so fancy algo- improves the runtime so much.

[agreen]

divmod() is a nice method for your isDivisor() function. It returns both the integer division result and the remainder as a tuple.

divmod(5, 2) = (2, 1)

[reverseila]

How is this easy. I'm starting leetcode and the first 2 so far was a bit hard

[twezo]

this isn't easy, I used recursion. But thank you for the explanation just so I can see how others solve it. I know eventually this will be easier for me.

[podilichaitanyaakhilkumar]

Keep uploading more leetcode problems as well as system design.

[jay]

There is a linear solution, based on the fact that str1 and str2 have a GCD string if and only if str1 + str2 == str2 + str1. But I fail to find a solution that explains why the right-to-left direction is true.

[jesuscruz]

This video helped explain it so well glad i watched

[krkode]

im confused on the big o explaination could someone explain it? i would have thought itd just be m cause isDivisor is just refactored out of the main loop its not like a smaller loop right.

[error-myut]

i thought of this approach was thinking why no one did this instead of str1+str2, like every soln has that code only idk why?

[bandhammanikanta]

Neetcode and NeetcodeIO are two different account?

[indie_gem]

how about if we use ascii to find the gcd?

[binh]

My brute force haha :P

def gcdOfStrings(self, str1: str, str2: str) -> str:
if len(str1) < len(str2):
str1, str2 = str2, str1
# str1 will always be the larger

for i in range(len(str2)):
pattern = str2[0:len(str2) - i]
if pattern in str1 and len(str1) % len(pattern) == 0 and len(str2) % len(pattern) == 0 and pattern * int((len(str1) / len(pattern))) == str1 and pattern * int((len(str2) / len(pattern))) == str2:
return pattern
return ""

[ramyhussein]

An easier solution:

def gcdOfStrings( str1, str2):

if str1 + str2 != str2 + str1:
return ""
# initializa the maximum possible length of the GCD
max_length = min(len(str1), len(str2))

for length in range(max_length, 0, -1):
if len(str1) % length == 0 and len(str2) % length == 0:
return str1[:length]
return ""