blob: 6daeda16849fb2c111e00c4389ba08f8d0ab7702 (
plain)
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
27
28
29
|
// 1653. Minimum Deletions to Make String Balanced
#include "leetcode.h"
/*
* you are given a string 's' consisting of only 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.
*/
int minimumDeletions(char *s) {
int cnt = 0, ans = 0;
for (int i = 0; s[i] != '\0'; i++) {
if (s[i] == 'b') {
cnt++;
} else if (cnt) {
ans++;
cnt--;
}
}
return ans;
}
int main() {
char *s1 = "aababbab", *s2 = "bbaaaaabb";
printf("%d\n", minimumDeletions(s1)); // expect: 2
printf("%d\n", minimumDeletions(s2)); // expect: 2
}
|