Word Subsets - Leetcode 916 - Python

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

Key Takeaways

The video demonstrates a solution to the Word Subsets problem on Leetcode, utilizing a hashmap to efficiently filter words based on subset conditions. The solution involves merging hashmaps from the second list of words and comparing character counts to determine subset relationships.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem word subsets this problem for how easy it is it's kind of deceptively difficult almost so we're given two lists of words so this is the first one and this is the second one and we basically want to filter the first list of words on this condition for this word if every single string in the second list of words is a subset set of this one then we will include this word in the output now how do we check if it's a subset for example how do we know that this is a subset of uh the character e basically does e show up in this string it does not so e is not a subset of Amazon So based on that alone we know that this is not going to be included in the output now what if we were checking for the character a a does show up in in this string so a technically would be a subset of Amon what about two A's well there are definitely two A's in this string so this or this is a subset of this string if it was Three A's though Three A's do not show up in the string Amon so this would then not be a subset of that so the count of each character from this string is basically what we are checking and in this problem I believe we are only dealing with lowercase A through Z so we filtered the first word we know we're not including Amazon in the output but then we would check the uh next word Apple does e show up in apple yes does o show up in apple nope so apple does not show up in the output for Facebook e does show up and O does show up as well so Facebook is included Google is also included bleet code is also included so at first it seems like the Brute Force solution is the best that we can do and what exactly would the RO for solution B well for every single word we could just get the count of every character so for example for Amazon we would say that the character a occurs twice M occurs a single time Z occurs a single time o also occurs a single time and N I'm running out of room so I'll put it up here shows up a single time for every word in the second uh list we want to do the same thing we want to convert it so e we would say it shows up a single time that's the whole word so these words aren't super interesting but you can imagine that they could have been actual words with multiple characters and so just imagine if that was the case we would have like let's say an m and like an N so what we would want to do is check all of these characters and make sure that the count of that character is less than or equal to the corresponding character in the other account so I could use a hashmap for this I could think I could also use an array if I wanted to but it's easier just to use a hashmap in my opinion so if we do this this basically what we're going to end up doing is going through every character in every word from the first list so you could call that like o of n times the average length of the word in that list but then we're also going to be going through every single word in the second list but we're going to have to go through like the hashmap for every single word in the second list we're going to have to do that for every word in the first list with like The Brute Force solution so that time complexity of that is not just going to be M * let's say L2 where that's like the length of the average word in the second list but we're going to have to do that n times so this is going to be the time complexity of the most root Force solution plus uh this I think at first it doesn't seem like there is a way to optimize it it's easier than you think I think that's why this is like deceptively difficult because what we want to do is basically just merge all of the hash maps from the second list of words like for example for the first word it's going to be e mapping to one for the second word it's going to be o mapping to one so we want to merge these two hash Maps when I say merge we want to kind of keep the max because we know for the first word we could say that e occurs once but o occurs exactly zero times in the second word we could say e occurs exactly zero times but o shows up once when we merge these we take the max so for E we see we have a one here and a zero here so by merging them we will keep the greater one so for o it shows up zero times or it shows up once we will keep the greater one and so now that we've taken all those hash Maps merged them into a single one where we kept the max for every single character if we can ensure that each of these counts the corresponding count in the other hashmap is greater than or equal to this count then we know that every single one of these work is a subset of that given word so this way we only need to iterate over all the characters of each word exactly a single time not literally exactly a single time but a linear amount of time for each uh string in the first uh list so this is how the algorithm is going to work we're going to go through every word in the second list we're going to create a single hash map for this entire list I'm going to call that let's say count two and then we're going to go word by word in the first list create a hashmap for this word and then let's just call that a count or whatever and then we're going to compare all the characters in this one to the counts in the first one and we can use some kind of flag to make sure that all of them show up in that and then if they all do then we will take that word and add it to the output list if they don't we will skip that word so this solution will be Big O of n * like the average length of the word in the first list plus plus uh M * the length 2 of the length of words in the second list so now let's code it up so what I'm going to do is first create a default dictionary of type int for count two so this is just a hashmap where the default value is going to be an integer of zero so I'm going to go through every word in the second list so like this and then I'm going to get the count of that word so the easiest way to do that actually is in Python you can use a counter I covered this I think in my python for coding interview scores and so I'm going to call this count W and then we want to merge this count in this hashmap up above so I'm going to go through every character count pair in this hashmap uh I can do that like this in python. items and then for count two I'm going to set for this count it to be the maximum of itself so count two of this character and the current count for that same character that we are looking at right now in the other hash so now that I have that I can then create my list of result output Words which I'm going to then uh return here so now I'm going to go through words in the first list I'm going to get the count of that word so count W of that word now so this line is pretty much the same as we have up above but now we want to compare so I'm going to have a flag I'm going to initially set it to true that means the count is good but inside the loop we're going to do this so we're going to go through every character account in the count two do items and we want to do the comparison so we want to make sure that the count of this character uh in the word that we're looking at right now is greater than or equal to the count of that character in the other hashmap the merged hash map we want this to be true but if this is not true what we're going to do is break out of the loop but before we break out of the loop we're going to set the flag to be false so if we never execute this line of code then we can ensure that all of these words were indeed a subset of the current word in which case out here we can say if the flag is still true then to the result append that word so this is the entire code let me just fit it all in one screen now let's run this and you can see it works and it's pretty efficient if you found this helpful check out n code. for a lot more thanks for watching and I'll see you soon

Original Description

🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews 🧑‍💼 LinkedIn: https://www.linkedin.com/in/navdeep-singh-3aaa14161/ 🐦 Twitter: https://twitter.com/neetcode1 ⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf Problem Link: https://leetcode.com/problems/word-subsets/ 0:00 - Read the problem 1:53 - Drawing Explanation 6:07 - Coding Explanation leetcode 916 #neetcode #leetcode #python
Watch on YouTube ↗ (saves to browser)
Sign in to unlock AI tutor explanation · ⚡30

Playlist

Uploads from NeetCodeIO · NeetCodeIO · 0 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
 14 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

The video teaches how to solve the Word Subsets problem on Leetcode using a hashmap to efficiently filter words based on subset conditions. The solution involves merging hashmaps and comparing character counts.

Key Takeaways
  1. Create a hashmap to store character counts for each word in the second list
  2. Merge hashmaps from the second list to create a single hashmap
  3. Compare character counts between the merged hashmap and each word in the first list
  4. Use a flag to track whether all characters in the word are subsets of the current word
  5. Append words that meet the subset condition to the result list
💡 Merging hashmaps from the second list allows for efficient comparison of character counts and determination of subset relationships

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:53 Drawing Explanation
6:07 Coding Explanation
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →