Minimum Deletions to Make String Balanced | Multiple Approaches | Leetcode 1653 | codestorywithMIK
426Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 22nd Video of our Playlist "Stack : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a very good Stack based problem : Minimum Deletions to Make String Balanced | Multiple Approaches | Dry Run | Leetcode 1653 | codestorywithMIK
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 : Minimum Deletions to Make String Balanced | Multiple Approaches | Dry Run | Leetcode 1653 | codestorywithMIK
Company Tags : will update soon
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/minimum...
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 :
Approach 1: Using a Stack
Time Complexity: O(n)
Space Complexity: O(n)
Description: This approach uses a stack to keep track of the characters. When encountering a 'ba' sequence, it pops the stack and increments the deletion count. This ensures the minimum deletions required to remove all 'ba' sequences in the string.
Approach 2: Three Passes + O(2 * n) Space
Time Complexity: O(3*n)
Space Complexity: O(2*n)
Description: This approach uses two auxiliary arrays, left_b and right_a, to count the number of 'b's to the left and 'a's to the right of each character in the string. By summing the values from these arrays for each position, it calculates the minimum deletions required to remove all 'ba' sequences.
Approach 3: Two Passes + O(n) Space
Time Complexity: O(2*n)
Space Complexity: O(n)
Description: This approach optimizes space by using a single auxiliary array right_a to count the number of 'a's to the right of each character. It then iterates through the string, keeping a running count of 'b's encountered so far, and computes the minimum deletions required by summing this count with the values in right_a.
Approach 4: Constant Space
Time Complexity: O(2*n)
Space Complexity: O(1)
Description: This approach further optimizes space usage by not using any auxiliary arrays. Instead, it counts the total number of 'a's in the string first, then iterates through the string while maintaining a running count of 'b's and decrementing the count of remaining 'a's as it encounters them. It computes the minimum deletions required using these counts.
✨ Timelines✨
00:00 - Introduction
#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