Greatest Common Divisor of Strings - Leetcode 1071 - Python

[@girishnakate5014]

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

[@NeetCodeIO]

Well normally I just do the daily LC problems, so difficulty is usually out of my control 😅

[@def__init]

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

[@NeetCodeIO]

Yeah, this is definitely difficult for an easy

[@hithambasheir3283]

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 🥳

[@Snoresville]

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

[@zeta_meow_meow]

damn bro , discuss section is surely amazing

[@axelstahl4386]

It’s because they all have to be made up of the same stuff. Like aa + a=a+aa cause it’s just a repeated. But b + a != a + b because it’s not one thing repeated, or a factor

[@sheeniebeanie2597]

class Solution: def gcdOfStrings(self, str1: str, str2: str) -> str: if str1 + str2 == str2 + str1: x = gcd(len(str1),len(str2)) return str1[:x] else: return ""

[@zaidnissar356]

Holy frick that is an insane solution. My mind is blown!!

[@iameenr]

​@@sheeniebeanie2597Phenomal 😮 How can one come up with such ideas!

[@BRBallin1]

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

[@lamborghinicentenario2497]

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))]

[@kingkidc2844]

The solution in this video isn't right for all cases return str1[:l] * p == str1 and str2[:l] * q == str2 this code should be switched to return str1[:l] * p == str1 and str1[:l] * q == str2 so it compares the substring str1 with str2

[@lassekock4315]

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

[@s.w.3077]

Both are str1[:l] multiplies by the factors f1 and f2.

[@tranminhquang4541]

lol this is more on the medium side

[@agreen254]

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)

[@PrajaktaKarandikar-t3w]

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

[@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.

[@podilichaitanyaakhilkumar4911]

Keep uploading more leetcode problems as well as system design.

[@jay5929]

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.

[@sheeniebeanie2597]

i made the linear solution--it worked in leetcode but dk if it works generally

[@ramyhussein4091]

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 ""

[@deionshepherd1331]

this is the solution i found as well but wondering if im missing any one offs

[@jesuscruz8008]

This video helped explain it so well glad i watched

[@sreeharshams905]

Thank you for this! Do you think we need to handle a case where both strings are equal, to return either one of them? def is_equal(s1, s2): return s1 == s2 if is_equal(str1, str2): return str1

[@kelvinjohndomeh1488]

How is this easy at the first place..naaaa

[@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 ""

[@zeta_meow_meow]

not that easy i guess 😅

[@bandhammanikanta]

Neetcode and NeetcodeIO are two different account?

[@kirillzlobin7135]

Awesome quality content

[@bernardwodoame9850]

I think I have to watch it again... I got lost .

[@KeyanSong-br5li]

Thank u!

[@error-my9ut]

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?

[@indie_gem]

how about if we use ascii to find the gcd?

[@krkode8765]

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.

[@Dudu-n4j]

class Solution: def gcdOfStrings(self, str1: str, str2: str) -> str: def gcd(a,b): while b: a,b = b, a%b return a gcd_len = gcd(len(str1),len(str2)) candidate = str1[:gcd_len] if str1 == candidate * (len(str1) // gcd_len) and str2 == candidate * (len(str2) // gcd_len): return candidate return ""

[@noaht9184]

This should be a medium bruh

[@sagark4080]

Time Complexity of below soln: O(logn)

[@prerittameta]

Please correct the code as it would fail for str1 = 'ABCD' str2 = 'DEFH' the correction in line 9 should be as below return str1[:l]*f1 == str1 and str2[:l]*f2 == str2 and str1[:l] == str2[:l]

[@hi-io]

It seems to me that it might not always work out, because str1 and str2 do not always follow the same order

[@effortlessjapanese123]

hey can you explain why we need to add str1[:l] == str2[:l]?

[@rashzh5502]

🔥🔥🔥

[@lamborghinicentenario2497]

This code only passes 21 out of 123 test cases on leetcode

[@KurtPhebus-b2s]

Austin Lake

[@omaryahia]

wow, nice

[@DodieMungo-y1x]

Constance Rue

[@samuelbanya]

4:14 Man, what am I even looking at? It's not even psuedo math that makes any sense whatsoever. If you had put something like 6 = 2x, it's basic algebra sure. But wow, that is an awful explanation in comparison, and I would suggest maybe redoing this video's section to be more clear. The problem itself is the worst word salad I have ever read in my entire life, but this solution is even more convoluted.

[@omaralzakout4100]

Bro, there is a more efficient solution that takes 2 lines of code in c++. Suppose the first string is s and the second is t then: string gcdOfStrings(string s, string t) { if(s+t != t+s) return ""; return s.substr(0, __gcd((int)s.size(), (int)t.size())); }