Largest Substring Between Two Equal Characters - Leetcode 1624 - Python

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

Key Takeaways

The video demonstrates a solution to the Leetcode 1624 problem, 'Largest Substring Between Two Equal Characters', using a hash map to track the first occurrence of each character in the string and calculate the maximum length of the substring between two equal characters. The solution is implemented in Python and has a time complexity of O(n) and a memory complexity of O(1).

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem largest substring between two equal characters we're given a string s which consists of only lowercase characters A through Z and we want to find the length of the substring between two characters that are equal so the longest substring that we can find like that so imagine we have a string like a b c d e a b c and then B to find a substring first we have to find two copies of the same character suppose these two they're both a what's the length of this substring and when they say length of substring they actually mean only the characters in between them so how many characters are between them well in this case there are four so is this the longest such substring because all we have to do is return the length of the longest substring there are two B's as well so we have a b here and a b here the number of characters between them is five and I think we also have two C's but the number of characters between them is three so obviously the longest is five that's what we would return now the question is how can we find the solution to this problem like how do we find that longest substring the first way that you might try is like a Brute Force approach for example starting at this a keep basically two pointers keep one pointer here and then this pointer will keep shifting through the string until it lands at another a and then we'll take the length between these two but one thing I think this problem actually doesn't clarify or at least doesn't make clear is what if we actually had another a over here does it allow us to consider this but also to consider this even though there's an a between them like does the characters in between have to be nonas in this problem actually this is perfectly valid it doesn't matter if there's an A in between these two there doesn't need to be other characters only it's a little open open ended but I think this sentence does uh support that knowing that the approach that I was kind of talking about right now is a Brute Force approach where we'd consider this character and then we'd consider this next character and then we'd consider the next character and keep going that would be an O of N squared approach but is it possible for us to do better is it possible for us to do this problem in a single pass well it would be hard with two pointers wouldn't it if we had one pointer here and we're iterating over these yes we know we've seen a b we know we've seen a d a c but by the time we get to this C for example how do we know that we have already seen a c before we'd have to probably put these characters somewhere in memory but not only that we'd have to also remember at what index did we see the C and it would be at index 0 1 two and of course we would probably know which index we're currently at we can do that with a single index or pointer I so if we can find a way to keep track of all the characters that we've seen before and map them to the index that we've seen we can solve this problem there's one last Edge case though and that is let's say the third occurrence of an a character over here we have actually seen two A's before so when we're here how do we want to calculate the window do we want to calculate it with the last a that we've seen or do we want to calculate it with the first a that we've seen probably the first a so when we take these guys and throw them into the data structure that we're going to use which in my case I'm going to use a hash map because like I said we want to map every character to the index so a would be mapped to zero B would be mapped to one etc etc when we get to the second occurrence of the a yes we're going to calculate the length of the substring we're going to see okay there's four characters in between them and by the way we would do that with 0 over here I think this is going to be a five we'd say 5 - 0 and then minus another one because we're only counting the characters in between them so that's going to be the formula by this point though when we get to the second a we calculate the length of the substring but we don't take this a and throw it in the hash Mount because there's already an a there we only want to keep track of the first occurrence of each character that will allow us to solve this problem optimally and we will do it in bigo of n time in terms of memory complexity you might think it's Big O of n but recall that the input string will only contain lowercase A through Z so that's technically 26 so this is actually constant memory now let's code this up so the first thing I'm going to do is create that hashmap where we are mapping every character to the first index that it occurs at so I'm going to call this map character index it's going to be just an empty hash map initially we also know that we're trying to calculate the max length between characters equal characters so that is going to be our result I'm not going to initialize it to zero because actually they tell us in the problem description that we should return netive -1 if a valid result does not exist so that is what I'm going to initialize it to I'm going to return it here and now the only thing left for us to do is actually calculate it I'm going to do a little shortcut in Python I see in enumerate this string if we were to iterate over this string we could iterate over just the character or we could just get the index by doing a range function and taking the length of this string but we can get both of those in one line if we use enumerate I'm going to do that and now we know that there's a couple cases have we seen this character before is this character in the character index map or is it not in the character index map we know the else case is pretty easy because if it's not the only thing for us to do is just throw it in there put this character and say that this is the first index that it occurs at we can't calculate the length of a substring because we've only seen this character once so far but this case is a bit more interesting if the character already exists here and now we have seen it again that means we can calculate the length between these two characters how do we do it well we take the index of the current character I subtracted by the index of the first time that we saw this character and also subtract one from it to get the number of characters in between them and this is the length between them now we want to maximize our result so we set result equal to the max of itself and what the current length between the characters happens to be this is the entire code let's run it to make sure that it works as you can see on the left yes it does run time doesn't look good but that's pretty random on leak code so I'm not going to pay attention to it if you found this helpful please like And subscribe if you're preparing for coding interviews check out ncode doio 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/ 🥷 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://leetcode.com/problems/largest-substring-between-two-equal-characters/ 0:00 - Read the problem 0:12 - Drawing Explanation 4:43 - Coding Explanation leetcode 1624 #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 Leetcode 1624 problem using a hash map to track the first occurrence of each character in the string and calculate the maximum length of the substring between two equal characters. The solution is implemented in Python and has a time complexity of O(n) and a memory complexity of O(1).

Key Takeaways
  1. Create a hash map to store the first occurrence of each character in the string
  2. Iterate over the string using enumerate to get both the character and index
  3. Check if the character is already in the hash map and calculate the length of the substring if it is
  4. Update the maximum length of the substring if the current length is greater
  5. Return the maximum length of the substring or -1 if no valid result exists
💡 Using a hash map to track the first occurrence of each character in the string allows for an efficient solution with a time complexity of O(n) and a memory complexity of O(1).

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
0:12 Drawing Explanation
4:43 Coding Explanation
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →