LeetCode 1653 | Minimum Deletions to Make String Balanced | Java | Medium | D P | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 1653 — Minimum Deletions to Make String Balanced using Dynamic Programming and Stack techniques in Java.
A string consisting of characters a and b is balanced if no character b appears before any character a. This structural constraint implies that all balanced strings must partition into a prefix of a's followed by a suffix of b's. Instead of testing all possible split points with prefix and suffix frequency arrays, we can maintain the optimal answer incrementally in a single pass.
By tracking the number of b characters seen so far, each time we encounter an a we face a clear binary decision: either delete the current a (incrementing total deletions by 1) or keep it (which requires deleting all preceding b characters). Taking the minimum of these two choices at each step guarantees the global minimum number of deletions in optimal linear O(n) runtime and O(1) auxiliary space.
🔥 Problem Highlights
✅ Characterized the canonical structure of balanced strings as a's followed by b's
✅ Reduced the decision space to an incremental single-pass dynamic programming transition
✅ Avoided extra space allocations by tracking states with two primitive integer variables
✅ Provided dual intuition through stack-based greedy deletion of invalid ba pairs
✅ Clean, idiomatic Java implementation
✅ Achieved optimal O(n) time and O(1) auxiliary space complexity
⏱️ TIMESTAMPS
00:00 Intro
00:55 Problem Understanding & Constraints
01:44 Inversion Triggers & Binary Choice Insight
03:12 State-Compressed Dynamic Programming Strategy
04:07 Java Code Walkthrough
05:07 Execution & Test Cases
06:37 Time Complexity Analysis (O(n))
07:20 Space Complexity Analysis (O(1))
07:44 Outro & Wrap-up
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/February/7-February/1653-Minimum-Deletions-to-Make-String-Balanced
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/7-February/1653-Minimum-Deletions-to-Make-String-Balanced/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/7-February/1653-Minimum-Deletions-to-Make-String-Balanced/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/7-February/1653-Minimum-Deletions-to-Make-String-Balanced/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/7-February/1653-Minimum-Deletions-to-Make-String-Balanced/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Medium Problems
Java DSA Preparation
Dynamic Programming on Strings
Stack and Greedy Patterns
String Manipulation Invariants
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
When iterating through string s, why does encountering a character 'b' never increase the current minimum deletions count?
1️⃣ Because appending 'b' to any balanced string ending with 'a' or 'b' can never create an invalid "ba" pair
2️⃣ Because 'b' characters cannot be deleted according to problem rules
3️⃣ Because 'b' characters have lower ASCII values than 'a'
4️⃣ Because we always delete all 'a' characters first
#LeetCode1653 #LeetCode #MinimumDeletionsToMakeStringBalanced #Java #JavaDSA #String #DynamicProgramming #Stack #Greedy #PrefixSum #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
In today’s video, we solve LeetCode 1653 — Minimum Deletions to Make String Balanced using Dynamic Programming and Stack techniques in Java.
A string consisting of characters a and b is balanced if no character b appears before any character a. This structural constraint implies that all balanced strings must partition into a prefix of a's followed by a suffix of b's. Instead of testing all possible split points with prefix and suffix frequency arrays, we can maintain the optimal answer incrementally in a single pass.
By tracking the number of b characters seen so far, each time we encounter an a we face a clear binary decision: either delete the current a (incrementing total deletions by 1) or keep it (which requires deleting all preceding b characters). Taking the minimum of these two choices at each step guarantees the global minimum number of deletions in optimal linear O(n) runtime and O(1) auxiliary space.
🔥 Problem Highlights
✅ Characterized the canonical structure of balanced strings as a's followed by b's
✅ Reduced the decision space to an incremental single-pass dynamic programming transition
✅ Avoided extra space allocations by tracking states with two primitive integer variables
✅ Provided dual intuition through stack-based greedy deletion of invalid ba pairs
✅ Clean, idiomatic Java implementation
✅ Achieved optimal O(n) time and O(1) auxiliary space complexity
⏱️ TIMESTAMPS
00:00 Intro
00:55 Problem Understanding & Constraints
01:44 Inversion Triggers & Binary Choice Insight
03:12 State-Compressed Dynamic Programming Strategy
04:07 Java Code Walkthrough
05:07 Execution & Test Cases
06:37 Time Complexity Analysis (O(n))
07:20 Space Complexity Analysis (O(1))
07:44 Outro & Wrap-up
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/February/7-February/1653-Minimum-Deletions-to-Make-String-Balanced
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/7-February/1653-Minimum-Deletions-to-Make-String-Balanced/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/7-February/1653-Minimum-Deletions-to-Make-String-Balanced/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/7-February/1653-Minimum-Deletions-to-Make-String-Balanced/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/7-February/1653-Minimum-Deletions-to-Make-String-Balanced/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Medium Problems
Java DSA Preparation
Dynamic Programming on Strings
Stack and Greedy Patterns
String Manipulation Invariants
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
When iterating through string s, why does encountering a character 'b' never increase the current minimum deletions count?
1️⃣ Because appending 'b' to any balanced string ending with 'a' or 'b' can never create an invalid "ba" pair
2️⃣ Because 'b' characters cannot be deleted according to problem rules
3️⃣ Because 'b' characters have lower ASCII values than 'a'
4️⃣ Because we always delete all 'a' characters first
#LeetCode1653 #LeetCode #MinimumDeletionsToMakeStringBalanced #Java #JavaDSA #String #DynamicProgramming #Stack #Greedy #PrefixSum #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
