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.
1def minDeletionsToMakeBalanced(s: str) -> int:
2 total_b = s.count('b')
3 min_deletions = total_b
4 current_a = 0
5 current_b = 0
6
7 for char in s:
8 if char == 'a':
9 current_a += 1
10 elif char == 'b':
11 current_b += 1
12 min_deletions = min(min_deletions, current_a + (total_b - current_b))
13
14 return min_deletions
15
16# Example Usage
17s = "aababbab"
18print(minDeletionsToMakeBalanced(s)) # Output: 2In Python, this implementation utilizes built-in list processing to count 'b's initially and dynamically updates minimum deletions using current counts of 'a's and remaining 'b's.