Greatest Common Divisor of Strings - Leetcode 1071 - Python

NeetCodeIO · Intermediate ·⚡ Algorithms & Data Structures ·3y ago

Key Takeaways

The video solves the Greatest Common Divisor of Strings Leetcode 1071 problem using a brute force approach and a greedy approach, implementing the solutions in Python.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem greatest common divisor of strings we're given two strings s and t and we say that t divides s if and only if one of the strings can be made up by adding the other string multiple times we could add it twice or three times or more times maybe even the two strings could be equal now given two strings our goal is to return the largest string X such that it divides both of these strings now that doesn't necessarily mean that string two will divide string one because as we can see from this second example we can't add this string twice to make this string but there exists a substring a b which can make this ring by adding it twice and can make this string by adding it three times and also don't let the problem trick you into assuming that string 1 is going to be longer than string two that's not necessarily going to be the case they just tell us we're given two arbitrary strings now there are many ways to solve this problem some can go really deep into the math but I'll keep it pretty intuitive you don't need super fancy math for my solution so how can we even Brute Force this problem well we can't just come up with our own random substring X let's try to take a substring from one of these two strings such as this one we can try a itself we can try this one it's length of one let's see if taking this and creating four copies of it because this string is length four we have to create four copies of this does that create this string well that would create a a a a a a that does not equal this string next we could try the first two characters which is of length two so how many times would we need to add it to make this string well we would need to add it twice because this is of length four so this is kind of where the math intuition comes in first of all we're trying substrings from this one why did I choose this one well because it's shorter than this one we know that if we get all the way up until here like this entire string and we tried every previous substring and none of those worked then creating a longer substring than this isn't going to work that type of X added together will never create this string because adding them together we have to create this string and we have to create this string so that's why we go with the smaller one though it doesn't make a huge difference I think but more importantly when we have a candidate X we take the length of this candidate X and we want to make sure that it is a factor of the length of this string because if it's not then it will be impossible to create this string such as for example if we had this string of length three adding this together will never create a string of length four we will though be be able to create a string of length 6 but that's not our goal here we need an X that can create both of these strings so another way to put it is when we have an X we take that length of it and we make sure that the length of this string which let's call L1 we can mod it by this length and when we mod it by this length there should not be a remainder so this should equal zero if it's not equal to zero we're not even going to try this candidate and we want to make sure the Sam is true for the other string too so we make sure to mod it by the length if it's not equal to zero then we don't do it but if it is equal to zero then we consider it and how exactly do we consider it well when we have a candidate like X how many times would we have to add X together to create a string of length four well we can get that by taking 4 and dividing it by the length of this candidate which is 2 that gives us two times two times x is going to create this string what about this guy well it has a length of six so we take six divided by two which we get the two from the length of X and then we get three so we need three copies of it to create this string and then all we do is check and then we just add it two times is it equal to this and add it three times is it equal to this guy if it is then we return the result one last thing we can do is that instead of going from smallest to largest we can be a bit greedy and try the longest possible one first because remember we're trying to find the largest X so let's start being greedy let's start with the four well four doesn't divide with six so we can't even try it then we try three well it doesn't divide with four then we try two yes it divides both of them and it does create both of them so that's what we would return immediately so to analyze the time complexity quickly since we're going to be iterating through the smaller string and checking in the worst case every sub substring of that that's going to be our X candidate we'll say that to do that we're going to need to iterate between the minimum of M and N where let's say m is the length of this guy and N is the length of this guy and then every time we do that in the worst case given a candidate X we're going to need to build this entire string which is of length n and we're going to need to build this entire string which is of length M and the time complexity to do that is going to be n plus M and we multiply these two together because this is what we're going to call inside of that Loop so this is the overall time complexity now let's code it up so we're going to start with the length of each substring and then we're going to iterate through where L this is an L maybe I should make a capital ball leave it lowercase for now L is in the range of the minimum of length 1 and length two and then we want to check if is divisor I'm going to create a helper function to do do this where the substring we can pick either one string one or string two because if it's a divisor of one it has to be a divisor of the other so we'll pick just arbitrarily starting with string one so a substring going from the beginning all the way to l oh and I forgot with our Loop we want to actually iterate not starting from zero but we want to start at the number itself and then iterate down going down negative one each time but this substring we picked it from string one we could have picked it from string two and the result would be the same because remember X whatever it is it has to go into both of the strings and that's what we're going to check in our is divisor function now if this were to return true that would mean we found our result because we're doing this in a greedy way so we would just return that string string one going from the beginning up until L and if we never find it out here then we can just return an empty string I think that's the default now to actually Define find our helper function let's call it is divisor it'll be given some length L first we want to check that L is a factor of the length of both strings the easy way to check that is length One modded by L so if this is non-zero or if this is non-zero then we know it's not a factor because it has to be zero so if it's not a factor of both of the strings then we just return immediately false we know it's not a divisor of both strings but if it is well at least the length of it is a divisor then we want to actually try to build the string but how do we build the string well I'm going to create a couple variables F1 and F2 these are going to be like the factors I guess I should write out the entire variable but I really hate writing out variables in leak code so to get F1 we're just going to take the length of string one and divide It by L we're doing integer division in Python because we need to round down while this would never be a decimal anyway because we made sure that it is a factor so I guess you don't really need that but I'll leave it anyway L2 divided by L so these are going to be the factors this is going to tell us how many times we have to multiply so when we take string that substring we were talking about our candidate L this is it we're going to multiply that by f 1 and we want to make sure that this is equal to string one and we also want to make sure that this is true for string two so here we just change this to F2 and we change this to string two you could say we need to change this to string two you could it would work but it'll work in both cases because remember our candidate is going to be the same for both strings anyway and if both of these are true we return true if they're not we return false so we can literally just return this entire value oh and I quickly I just noticed that here we're passing in the string we don't want to do that we want to pass an L itself so this is is the entire code let's run it to make sure that it works and as you can see yes it does and it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neat code.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon

Original Description

🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews Solving Greatest Common Divisor of Strings Leetcode 1071, today's daily leetcode problem on January 31st. 🥷 Discord: https://discord.gg/ddjKRXPqtk 🐦 Twitter: https://twitter.com/neetcode1 🐮 Support the channel: https://www.patreon.com/NEETcode ⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf 💡 DYNAMIC PROGRAMMING PLAYLIST: https://www.youtube.com/watch?v=73r3KWiEvyk&list=PLot-Xpze53lcvx_tjrr_m2lgD2NsRHlNO&index=1 Problem Link: https://neetcode.io/problems/greatest-common-divisor-of-strings 0:00 - Read the problem 1:10 - Drawing Explanation 5:32 - Coding Explanation leetcode 1071 #neetcode #leetcode #python
Watch on YouTube ↗ (saves to browser)
Sign in to unlock AI tutor explanation · ⚡30

Playlist

Uploads from NeetCodeIO · NeetCodeIO · 14 of 60

← Previous Next →
1 Leetcode 149 - Maximum Points on a Line - Python
Leetcode 149 - Maximum Points on a Line - Python
NeetCodeIO
 2 Design Linked List - Leetcode 707 - Python
Design Linked List - Leetcode 707 - Python
NeetCodeIO
 3 Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
NeetCodeIO
 4 Design Browser History - Leetcode 1472 - Python
Design Browser History - Leetcode 1472 - Python
NeetCodeIO
 5 Number of Good Paths - Leetcode 2421 - Python
Number of Good Paths - Leetcode 2421 - Python
NeetCodeIO
 6 Flip String to Monotone Increasing - Leetcode 926 - Python
Flip String to Monotone Increasing - Leetcode 926 - Python
NeetCodeIO
 7 Maximum Sum Circular Subarray - Leetcode 918 - Python
Maximum Sum Circular Subarray - Leetcode 918 - Python
NeetCodeIO
 8 Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
NeetCodeIO
 9 Concatenated Words - Leetcode 472 - Python
Concatenated Words - Leetcode 472 - Python
NeetCodeIO
 10 Data Stream as Disjoint Intervals - Leetcode 352 - Python
Data Stream as Disjoint Intervals - Leetcode 352 - Python
NeetCodeIO
 11 LFU Cache - Leetcode 460 - Python
LFU Cache - Leetcode 460 - Python
NeetCodeIO
 12 N-th Tribonacci Number - Leetcode 1137
N-th Tribonacci Number - Leetcode 1137
NeetCodeIO
 13 Best Team with no Conflicts - Leetcode 1626 - Python
Best Team with no Conflicts - Leetcode 1626 - Python
NeetCodeIO
 ▶ Greatest Common Divisor of Strings - Leetcode 1071 - Python
Greatest Common Divisor of Strings - Leetcode 1071 - Python
NeetCodeIO
 15 Shortest Path in a Binary Matrix - Leetcode 1091 - Python
Shortest Path in a Binary Matrix - Leetcode 1091 - Python
NeetCodeIO
 16 Insert into a Binary Search Tree - Leetcode 701 - Python
Insert into a Binary Search Tree - Leetcode 701 - Python
NeetCodeIO
 17 Delete Node in a BST - Leetcode 450 - Python
Delete Node in a BST - Leetcode 450 - Python
NeetCodeIO
 18 Shuffle the Array (Constant Space) - Leetcode 1470 - Python
Shuffle the Array (Constant Space) - Leetcode 1470 - Python
NeetCodeIO
 19 Fruits into Basket - Leetcode 904 - Python
Fruits into Basket - Leetcode 904 - Python
NeetCodeIO
 20 Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
NeetCodeIO
 21 Naming a Company - Leetcode 2306 - Python
Naming a Company - Leetcode 2306 - Python
NeetCodeIO
 22 As Far from Land as Possible - Leetcode 1162 - Python
As Far from Land as Possible - Leetcode 1162 - Python
NeetCodeIO
 23 Shortest Path with Alternating Colors - Leetcode 1129 - Python
Shortest Path with Alternating Colors - Leetcode 1129 - Python
NeetCodeIO
 24 Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
NeetCodeIO
 25 Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
NeetCodeIO
 26 Contains Duplicate II - Leetcode 219 - Python
Contains Duplicate II - Leetcode 219 - Python
NeetCodeIO
 27 Path with Maximum Probability - Leetcode 1514 - Python
Path with Maximum Probability - Leetcode 1514 - Python
NeetCodeIO
 28 Add to Array-Form of Integer - Leetcode 989 - Python
Add to Array-Form of Integer - Leetcode 989 - Python
NeetCodeIO
 29 Unique Paths II - Leetcode 63 - Python
Unique Paths II - Leetcode 63 - Python
NeetCodeIO
 30 Minimum Distance between BST Nodes - Leetcode 783 - Python
Minimum Distance between BST Nodes - Leetcode 783 - Python
NeetCodeIO
 31 Design Hashmap - Leetcode 706 - Python
Design Hashmap - Leetcode 706 - Python
NeetCodeIO
 32 Range Sum Query Immutable - Leetcode 303 - Python
Range Sum Query Immutable - Leetcode 303 - Python
NeetCodeIO
 33 Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
NeetCodeIO
 34 Middle of the Linked List - Leetcode 876 - Python
Middle of the Linked List - Leetcode 876 - Python
NeetCodeIO
 35 Course Schedule IV - Leetcode 1462 - Python
Course Schedule IV - Leetcode 1462 - Python
NeetCodeIO
 36 Single Element in a Sorted Array - Leetcode 540 - Python
Single Element in a Sorted Array - Leetcode 540 - Python
NeetCodeIO
 37 Capacity to Ship Packages - Leetcode 1011 - Python
Capacity to Ship Packages - Leetcode 1011 - Python
NeetCodeIO
 38 IPO - Leetcode 502 - Python
IPO - Leetcode 502 - Python
NeetCodeIO
 39 Minimize Deviation in Array - Leetcode 1675 - Python
Minimize Deviation in Array - Leetcode 1675 - Python
NeetCodeIO
 40 Longest Turbulent Array - Leetcode 978 - Python
Longest Turbulent Array - Leetcode 978 - Python
NeetCodeIO
 41 Last Stone Weight II - Leetcode 1049 - Python
Last Stone Weight II - Leetcode 1049 - Python
NeetCodeIO
 42 Construct Quad Tree - Leetcode 427 - Python
Construct Quad Tree - Leetcode 427 - Python
NeetCodeIO
 43 Find Duplicate Subtrees - Leetcode 652 - Python
Find Duplicate Subtrees - Leetcode 652 - Python
NeetCodeIO
 44 Sort an Array - Leetcode 912 - Python
Sort an Array - Leetcode 912 - Python
NeetCodeIO
 45 Ones and Zeroes - Leetcode 474 - Python
Ones and Zeroes - Leetcode 474 - Python
NeetCodeIO
 46 Remove Duplicates from Sorted Array II - Leetcode 80 - Python
Remove Duplicates from Sorted Array II - Leetcode 80 - Python
NeetCodeIO
 47 Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
NeetCodeIO
 48 Concatenation of Array - Leetcode 1929 - Python
Concatenation of Array - Leetcode 1929 - Python
NeetCodeIO
 49 Symmetric Tree - Leetcode 101 - Python
Symmetric Tree - Leetcode 101 - Python
NeetCodeIO
 50 Check Completeness of a Binary Tree - Leetcode 958 - Python
Check Completeness of a Binary Tree - Leetcode 958 - Python
NeetCodeIO
 51 Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
NeetCodeIO
 52 Find Peak Element - Leetcode 162 - Python
Find Peak Element - Leetcode 162 - Python
NeetCodeIO
 53 Accounts Merge - Leetcode 721 - Python
Accounts Merge - Leetcode 721 - Python
NeetCodeIO
 54 Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
NeetCodeIO
 55 Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
NeetCodeIO
 56 Number of Zero-Filled Subarrays - Leetcode 2348 - Python
Number of Zero-Filled Subarrays - Leetcode 2348 - Python
NeetCodeIO
 57 Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
NeetCodeIO
 58 Sqrt(x) - Leetcode 69 - Python
Sqrt(x) - Leetcode 69 - Python
NeetCodeIO
 59 Successful Pairs of Spells and Potions - Leetcode 2300 - Python
Successful Pairs of Spells and Potions - Leetcode 2300 - Python
NeetCodeIO
 60 Optimal Partition of String - Leetcode 2405 - Python
Optimal Partition of String - Leetcode 2405 - Python
NeetCodeIO

This video teaches how to solve the Greatest Common Divisor of Strings Leetcode 1071 problem using a brute force approach and a greedy approach, with implementations in Python. The problem requires finding the largest string X that divides both input strings s and t.

Key Takeaways
  1. Iterate over substrings of the shorter string
  2. Check if the length of the substring is a factor of the length of the longer string
  3. Calculate how many times the substring needs to be added to create the longer string
  4. Add the substring multiple times to create the longer string
  5. Use a helper function to check if a given length L is a divisor of both strings
  6. Build the string by dividing the length of one string by L and creating a substring of that length
💡 The problem can be solved using a brute force approach or a greedy approach, and the choice of approach depends on the time complexity and the size of the input strings.

Related AI Lessons

⚡
Bloom Filters, Explained Properly
Learn how Bloom filters work and their benefits, including tiny memory and blazing speed, in exchange for potential false positives.
Dev.to · Daksh Gargas
 ⚡
Prefix Sums: The Preprocessing Trick That Makes Range Queries Instant
Learn how prefix sums enable instant range queries in arrays, boosting performance in various applications
Medium · Programming
 ⚡
I Thought I Was Ready for the Interview — Then One Simple Math Question Destroyed Me
A simple math question can destroy a developer's interview, highlighting the importance of being prepared for unexpected questions
Medium · Programming
 ⚡
Week 2(Day 10): LeetCode Two Pointers(slow & fast): Remove Duplicates from Sorted Array (Brute…
Learn to remove duplicates from a sorted array using the two pointers technique, improving from brute force to optimized solutions
Medium · Python

Chapters (3)

Read the problem
1:10 Drawing Explanation
5:32 Coding Explanation
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →