Maximum Score From Removing Substrings | 2 Approaches | With Proof | Leetcode 1717
390iPAD PDF Notes - https://github.com/MAZHARMIK/Intervie...
Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 19th Video of our Playlist "Stack : Popular Interview Problems" by codestorywithMIK
Using Approach-2 (i and j pointer approach), you can solve this problem as well - https://leetcode.com/problems/check-i...
In this video we will try to solve a very good Stack based problem : Maximum Score From Removing Substrings | 2 Approaches | With Proof | Leetcode 1717 | codestorywithMIK
We will also prove why the solution works.
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Maximum Score From Removing Substrings | 2 Approaches | With Proof | Leetcode 1717 | codestorywithMIK
Company Tags : META, AMAZON, GOOGLE
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/maximum...
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Time Complexity: O(n)
Space Complexity: O(n)
In this approach, the solution leverages a stack to remove the specified substrings from the input string s. The algorithm proceeds in two main passes:
First Pass:
Identifies the substring (maxStr) that yields the higher score (max(x, y)) and removes it from s using the removeSubstring function.
The removeSubstring function uses a stack to track characters, removing pairs that match maxStr.
The score is updated by the number of removed pairs multiplied by the higher score value.
Second Pass:
The remaining string from the first pass is processed similarly to remove the substring (minStr) that yields the lower score (min(x, y)).
The score is again updated based on the number of removed pairs.
This method ensures that the higher score pairs are removed first, potentially increasing the overall score.
Approach 2: Without Stack
Time Complexity: O(n)
Space Complexity: O(1)
This approach optimizes space by removing the need for an auxiliary stack. Instead, it directly modifies the input string:
First Pass:
Similar to the first approach, it identifies and removes the maxStr substring from s.
Uses two pointers technique to keep track of valid characters in the string.
Updates the score based on the number of removed pairs multiplied by the higher score value.
Second Pass:
The modified string from the first pass is processed to remove the minStr substring.
Score is updated based on the number of removed pairs.
This approach achieves the same goal but with reduced space complexity, making it more efficient in terms of memory usage.
✨ Timelines✨
00:00 - Introduction
00:23 - Problem Explanation
02:11 - Approach-1 Thought Process (Using Stack)
08:49 - Proof of Approach-1
20:10 - Coding Approach-1
26:26 - Approach-2 Thought Process (Without Stack)
37:50 - Coding Approach-2
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024