# 1653. Minimum Deletions to Make String Balanced

## Description

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 <= 105
• s[i] is 'a' or 'b'​​.

## Solutions

Dynamic programming.

• class Solution {
public int minimumDeletions(String s) {
int n = s.length();
int[] f = new int[n + 1];
int b = 0;
for (int i = 1; i <= n; ++i) {
if (s.charAt(i - 1) == 'b') {
f[i] = f[i - 1];
++b;
} else {
f[i] = Math.min(f[i - 1] + 1, b);
}
}
return f[n];
}
}

• class Solution {
public:
int minimumDeletions(string s) {
int n = s.size();
int f[n + 1];
memset(f, 0, sizeof(f));
int b = 0;
for (int i = 1; i <= n; ++i) {
if (s[i - 1] == 'b') {
f[i] = f[i - 1];
++b;
} else {
f[i] = min(f[i - 1] + 1, b);
}
}
return f[n];
}
};

• class Solution:
def minimumDeletions(self, s: str) -> int:
n = len(s)
f = [0] * (n + 1)
b = 0
for i, c in enumerate(s, 1):
if c == 'b':
f[i] = f[i - 1]
b += 1
else:
f[i] = 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]
}

• 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.charAt(i - 1) === 'b') {
f[i] = f[i - 1];
++b;
} else {
f[i] = Math.min(f[i - 1] + 1, b);
}
}
return f[n];
}