Minimum Deletions to Make String Balanced solution and explanation
Google
9 more videos on this problem
Minimum Deletions to Make String Balanced | Multiple Approaches | Leetcode 1653 | codestorywithMIKcodestorywithMIK · 34:00 · 19K views
Minimum Deletions to Make String Balanced - Leetcode 1653 - PythonNeetCodeIO · 14:56 · 17K views
Minimum Deletions to Balance String | LeetCode 1653 | Prefix & Suffix CountingSanyam IIT Guwahati · 19:36 · 1K views
Daily Leetcode #2139: Feb 07, 2026 - 1653. Minimum Deletions to Make String BalancedProgramming Live with Larry · 6:35 · 592 views
1653. Minimum Deletions to Make String Balanced | Leetcode Daily - PythonLeetcode Daily · 9:53 · 547 views
Leetcode | 1653. Minimum Deletions to Make String Balanced | Medium | JavaDeveloper Docs · 5:55 · 502 views
Minimum Deletions to Make String Balanced | LeetCode 1653 | DP + Prefix Count Optimal Approach Study Placement · 13:05 · 456 views
Minimum Deletions to Make String Balanced - Leetcode 1653 - JavaCode With K5KC · 10:32 · 184 views
Minimum Deletions to Make String Balanced - Leetcode 1653 - PythonTim Huang · 3:31 · 106 views
One Pass Greedy Solution | Minimum Deletions to Make String Balanced | LeetCode 1653Daily Dose Of LeetCode · 22:29 · 90 views
The problem
You are given a string s consisting only of characters 'a' and 'b'.
You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.
Return the minimum number of deletions needed to make s balanced.
Example 1:
Input: s = "aababbab"
Output: 2
Explanation: You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or
Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").
Example 2:
Input: s = "bbaaaaabb" Output: 2 Explanation: The only solution is to delete the first two characters.
Constraints:
1 <= s.length <= 105s[i]is'a'or'b'.
Approach overview
Problem Overview: You are given a string containing only 'a' and 'b'. The string is balanced if no 'b' appears before an 'a' (no "ba" pattern). The task is to delete the minimum number of characters so the remaining string becomes balanced.
Approach 1: Split Point Enumeration (Brute Force) (Time: O(n^2), Space: O(1))
A balanced string effectively looks like a block of 'a' characters followed by a block of 'b' characters. Try every possible split index i in the string. For the left side, count how many 'b' characters must be deleted to keep only 'a'. For the right side, count how many 'a' characters must be deleted to keep only 'b'. The minimum deletions across all split points gives the answer. This approach demonstrates the key observation about the structure of a balanced string but recalculates counts repeatedly, leading to quadratic time.
Approach 2: Prefix Count and Dynamic Adjustment (Time: O(n), Space: O(1))
Traverse the string once while tracking two values: the number of 'b' characters seen so far and the minimum deletions needed to keep the prefix balanced. When you encounter 'a', you have two choices: delete this 'a' (cost deletions + 1) or delete all previous 'b' characters (cost bCount). Take the minimum. When you encounter 'b', simply increase bCount. This dynamic adjustment effectively simulates the optimal split point while scanning, making it a clean linear-time solution. The technique is closely related to prefix reasoning often used in string problems and lightweight dynamic programming.
Approach 3: Stack-Based Simulation (Time: O(n), Space: O(n))
You can also model the constraint using a stack. Iterate through the string and push 'b' characters onto the stack. When an 'a' appears after a 'b', the pair forms a violation ("ba"). You can either delete the current 'a' or remove a previous 'b' from the stack. By greedily resolving these conflicts while counting deletions, the algorithm maintains a valid order. This approach is conceptually intuitive for developers comfortable with stack patterns, though it uses extra memory compared to the prefix method.
Recommended for interviews: The prefix count and dynamic adjustment approach is the expected solution. It runs in O(n) time with O(1) space and clearly demonstrates the core insight: at every 'a', decide whether deleting the current character or all previous 'b' characters is cheaper. Starting with the brute-force split explanation helps communicate the reasoning before optimizing.
Approach 1: Prefix Count and Dynamic Adjustment
This approach involves using prefix sums to count the number of 'b's seen until each index and adjusting to track the potential number of deletions to ensure a balanced string.
def minDeletionsToMakeBalanced(s: str) -> int:
total_b = s.count('b')
min_deletions = total_b
current_a = 0
current_b = 0
for char in s:
if char == 'a':
current_a += 1
elif char == 'b':
current_b += 1
min_deletions = min(min_deletions, current_a + (total_b - current_b))
return min_deletions
# Example Usage
s = "aababbab"
print(minDeletionsToMakeBalanced(s)) # Output: 2public class MinDeletionsBalanced {
public static int minDeletionsToMakeBalanced(String s) {
int totalB = 0;
int minDeletions;
for (char c : s.toCharArray()) {
if (c == 'b') totalB++;
}
minDeletions = totalB;
int currentA = 0, currentB = 0;
for (char c : s.toCharArray()) {
if (c == 'a') {
currentA++;
} else if (c == 'b') {
currentB++;
minDeletions = Math.min(minDeletions, currentA + (totalB - currentB));
}
}
return minDeletions;
}
public static void main(String[] args) {
String s = "aababbab";
System.out.println(minDeletionsToMakeBalanced(s)); // Output: 2
}
}#include <iostream>
#include <string>
int minDeletionsToMakeBalanced(const std::string &s) {
int total_b = 0;
for (char c : s) {
if (c == 'b') total_b++;
}
int min_deletions = total_b;
int current_a = 0, current_b = 0;
for (char c : s) {
if (c == 'a') {
current_a++;
} else {
current_b++;
min_deletions = std::min(min_deletions, current_a + (total_b - current_b));
}
}
return min_deletions;
}
int main() {
std::string s = "aababbab";
std::cout << minDeletionsToMakeBalanced(s) << std::endl; // Output: 2
return 0;
}function minDeletionsToMakeBalanced(s) {
let totalB = 0;
for (let char of s) {
if (char === 'b') totalB++;
}
let minDeletions = totalB;
let currentA = 0;
let currentB = 0;
for (let char of s) {
if (char === 'a') {
currentA++;
} else if (char === 'b') {
currentB++;
minDeletions = Math.min(minDeletions, currentA + (totalB - currentB));
}
}
return minDeletions;
}
console.log(minDeletionsToMakeBalanced('aababbab')); // Output: 2#include <stdio.h>
#include <string.h>
int minDeletionsToMakeBalanced(char* s) {
int n = strlen(s);
int b_count = 0, min_deletions = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == 'b') b_count++;
}
int current_a_count = 0;
min_deletions = b_count; // Full deletion of 'b's
for (int i = 0; i < n; ++i) {
if (s[i] == 'a') {
current_a_count++;
} else { // s[i] == 'b'
b_count--;
}
min_deletions = min_deletions < current_a_count + b_count ? min_deletions : current_a_count + b_count;
}
return min_deletions;
}
int main() {
char s[] = "aababbab";
printf("%d\n", minDeletionsToMakeBalanced(s)); // Output: 2
return 0;
}using System;
public class MinDeletionsBalanced {
public static int MinDeletionsToMakeBalanced(string s) {
int totalB = 0;
foreach (char c in s) {
if (c == 'b') totalB++;
}
int minDeletions = totalB;
int currentA = 0, currentB = 0;
foreach (char c in s) {
if (c == 'a') {
currentA++;
} else if (c == 'b') {
currentB++;
minDeletions = Math.Min(minDeletions, currentA + (totalB - currentB));
}
}
return minDeletions;
}
public static void Main() {
string s = "aababbab";
Console.WriteLine(MinDeletionsToMakeBalanced(s)); // Output: 2
}
}In Python, this implementation utilizes built-in list processing to count 'b's initially and dynamically updates minimum deletions using current counts of 'a's and remaining 'b's.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1).
Approach 2: Dynamic Programming
We define f[i] as the minimum number of characters to be deleted in the first i characters to make the string balanced. Initially, f[0]=0. The answer is f[n].
We traverse the string s, maintaining a variable b, which represents the number of character 'b' in the characters before the current position.
- If the current character is 'b', it does not affect the balance of the first
icharacters, sof[i]=f[i-1], then we updateb \leftarrow b+1. - If the current character is 'a', we can choose to delete the current character, so
f[i]=f[i-1]+1; or we can choose to delete the previous character 'b', sof[i]=b. Therefore, we take the minimum of the two, that is,f[i]=min(f[i-1]+1,b).
In summary, we can get the state transition equation:
$
f[i]=\begin{cases}
f[i-1], & s[i-1]='b'\
min(f[i-1]+1,b), & s[i-1]='a'
\end{cases}
The final answer is f[n].
We notice that the state transition equation is only related to the previous state and the variable b, so we can just use an answer variable ans to maintain the current f[i], and there is no need to allocate an array f.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1)$.
function minimumDeletions(s: string): number {
const n = s.length;
const f = new Array(n + 1).fill(0);
let b = 0;
for (let i = 1; i <= n; ++i) {
if (s[i - 1] === 'b') {
f[i] = f[i - 1];
++b;
} else {
f[i] = Math.min(f[i - 1] + 1, b);
}
}
return f[n];
}func minimumDeletions(s string) int {
n := len(s)
f := make([]int, n+1)
b := 0
for i, c := range s {
i++
if c == 'b' {
f[i] = f[i-1]
b++
} else {
f[i] = min(f[i-1]+1, b)
}
}
return f[n]
}Approach 3: Enumeration + Prefix Sum
We can enumerate each position i in the string s, dividing the string s into two parts, namely s[0,..,i-1] and s[i+1,..n-1]. To make the string balanced, the number of characters we need to delete at the current position i is the number of character 'b' in s[0,..,i-1] plus the number of character 'a' in s[i+1,..n-1].
Therefore, we maintain two variables lb and ra to represent the number of character 'b' in s[0,..,i-1] and the number of character 'a' in s[i+1,..n-1] respectively. The number of characters we need to delete is lb+ra. During the enumeration process, we update the variables lb and ra.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the string s.
function minimumDeletions(s: string): number {
let lb = 0,
ra = 0;
let n = s.length;
for (let i = 0; i < n; ++i) {
if (s[i] === 'a') {
++ra;
}
}
let ans = n;
for (let i = 0; i < n; ++i) {
ra -= s[i] === 'a' ? 1 : 0;
ans = Math.min(ans, lb + ra);
lb += s[i] === 'b' ? 1 : 0;
}
return ans;
}func minimumDeletions(s string) int {
lb, ra := 0, strings.Count(s, "a")
ans := ra
for _, c := range s {
if c == 'a' {
ra--
}
if t := lb + ra; ans > t {
ans = t
}
if c == 'b' {
lb++
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Count and Dynamic Adjustment | Time Complexity: O(n), where n is the length of the string. |
| Dynamic Programming | – |
| Enumeration + Prefix Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Split Point Enumeration (Brute Force) | O(n^2) | O(1) | Good for understanding the structure of a balanced string and explaining the idea in interviews before optimization. |
| Prefix Count and Dynamic Adjustment | O(n) | O(1) | Optimal solution. Best for interviews and large inputs since it scans the string once. |
| Stack-Based Simulation | O(n) | O(n) | Useful when modeling ordering constraints with stack patterns or teaching the concept visually. |
Frequently asked questions
Is Minimum Deletions to Make String Balanced easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 68%. The difficulty comes from recognizing the ordering constraint and converting it into a prefix decision problem. Once the correct insight is found, the implementation is short and runs in linear time.
Minimum Deletions to Make String Balanced Python/Java solution
The O(n) solution works the same in Python, Java, C++, JavaScript, and C#. Maintain two variables: the count of 'b' characters seen and the minimum deletions so far. Update the deletion count when an 'a' appears using min(deletions + 1, bCount). This keeps the algorithm linear and memory efficient.
How to solve Minimum Deletions to Make String Balanced in O(n)?
Iterate through the string while tracking the number of 'b' characters seen so far. When you encounter 'a', update the minimum deletions as min(current deletions + 1, number of previous 'b'). This decision either deletes the current 'a' or removes earlier 'b' characters. Continue scanning until the end to obtain the minimum deletions.
What is the best approach for Minimum Deletions to Make String Balanced?
The prefix count and dynamic adjustment approach is the most efficient. Scan the string once while tracking how many 'b' characters have appeared and the minimum deletions required so far. When an 'a' appears after 'b', choose the cheaper option: delete this 'a' or delete the previous 'b' characters. This produces an O(n) time and O(1) space solution.
Is Minimum Deletions to Make String Balanced asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving greedy decisions and prefix-based dynamic programming on strings. Variants of this problem have appeared in interviews at large tech companies and are frequently practiced for Amazon, Google, and Meta preparation because it tests reasoning about ordering constraints.
What data structure is used in Minimum Deletions to Make String Balanced?
The optimal implementation mainly uses counters and prefix reasoning, which resembles a lightweight dynamic programming approach. Some alternative explanations use a stack to track previous 'b' characters and resolve 'ba' violations during traversal.
What is the time complexity of Minimum Deletions to Make String Balanced?
The optimal solution runs in O(n) time because the string is processed in a single pass. Only two counters are maintained during traversal, so the space complexity is O(1). Brute force approaches that recompute counts for each split can take O(n^2) time.