leetcode 1653 - Minimum Deletions to Make String Balanced

https://leetcode.com/problems/minimum-deletions-to-make-string-balanced/

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 <= 10^5
s[i] is ‘a’ or ‘b’

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int minimumDeletions(string s) {
int size = s.size();

vector<int> counts_a(size+1), counts_b(size+1);
counts_a[0] = 0;
counts_b[0] = 0;

for (int len = 1; len <= size; len++) {
int i = len - 1;
int j = size - len;

counts_b[len] = counts_b[len-1] + (s[i] == 'b' ? 1 : 0);
counts_a[len] = counts_a[len-1] + (s[j] == 'a' ? 1 : 0);
}

int deletions = INT_MAX;

for (int len = 0; len <= size; len++) {
deletions = min(deletions, counts_b[len] + counts_a[size-len]);
}

return deletions;
}
};