Sponsored
Sponsored
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.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since we're using constant space.
1#include <stdio.h>
2#include <string.h>
3
4int minDeletionsToMakeBalanced(char* s) {
5 int n = strlen(s);
6 int b_count = 0, min_deletions = 0;
7
8 for (int i = 0; i < n; ++i) {
9 if (s[i] == 'b') b_count++;
10 }
11
12 int current_a_count = 0;
13 min_deletions = b_count; // Full deletion of 'b's
14
15 for (int i = 0; i < n; ++i) {
16 if (s[i] == 'a') {
17 current_a_count++;
18 } else { // s[i] == 'b'
19 b_count--;
20 }
21 min_deletions = min_deletions < current_a_count + b_count ? min_deletions : current_a_count + b_count;
22 }
23
24 return min_deletions;
25}
26
27int main() {
28 char s[] = "aababbab";
29 printf("%d\n", minDeletionsToMakeBalanced(s)); // Output: 2
30 return 0;
31}This C solution iterates through the string once to count total 'b's. Then it iteratively calculates the minimum deletions needed by adjusting counts of 'a' seen and remaining 'b's using a greedy approach.