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.
1public class MinDeletionsBalanced {
2 public static int minDeletionsToMakeBalanced(String s) {
3 int totalB = 0;
4 int minDeletions;
5
6 for (char c : s.toCharArray()) {
7 if (c == 'b') totalB++;
8 }
9
10 minDeletions = totalB;
11
12 int currentA = 0, currentB = 0;
13
14 for (char c : s.toCharArray()) {
15 if (c == 'a') {
16 currentA++;
17 } else if (c == 'b') {
18 currentB++;
19 minDeletions = Math.min(minDeletions, currentA + (totalB - currentB));
20 }
21 }
22
23 return minDeletions;
24 }
25
26 public static void main(String[] args) {
27 String s = "aababbab";
28 System.out.println(minDeletionsToMakeBalanced(s)); // Output: 2
29 }
30}This Java solution employs a similar approach to the other two languages, using modern Java features for readability. It balances counting 'a's and remaining 'b's to determine where the least deletions occur.