1653. Minimum Deletions to Make String Balanced
Problem Description
In this problem, we are given a string s
which contains only two types of characters: 'a' and 'b'. Our goal is to make the string "balanced" by removing characters from the string. A string is considered to be "balanced" if there are no occurrences where a 'b' is followed by an 'a' at any point later in the string.
The objective is to find the minimum number of deletions required to achieve this balance. In other words, after all the deletions, anywhere you look in the string from left to right, if you see the character 'b', you should not expect to find the character 'a' following it anywhere in the rest of the string.
Intuition
To solve the problem, we need to understand what makes the string unbalanced. The string becomes unbalanced when there is a 'b' that occurs before an 'a' because the problem's condition is that no 'b' should come before an 'a'. So, we essentially need to either remove such 'b's or the 'a's that make them violate the condition.
A straightforward approach might be to remove all 'b's before an 'a', but this might not be optimal, as there might be a large number of 'b's followed by very few 'a's. Similarly, removing all 'a's after a 'b' may also not be optimal for the opposite reason. Hence, we need an approach that efficiently finds the balance by considering the distribution of 'a's and 'b's in the string.
Dynamic programming can be used to find such an optimal solution, but it might be too complex for this scenario. Observing that we only need minimal deletions, we can use a simple iterative approach. We'll go through the string and keep track of the count of 'b's we've seen so far. Each time we encounter an 'a', we have a choice - we can either delete this 'a' or all the 'b's before it. We choose the option that minimizes the total deletions.
The intuitive insight is that, as we scan the string, if we keep track of the number of deletions and the count of 'b's, we can always decide the best option at each step. This accumulates to the minimum number of deletions needed to balance the string by the end of the iteration over the string.
Learn more about Stack and Dynamic Programming patterns.
Solution Approach
The solution uses a simple linear scan approach that leverages two variables, b
and ans
, to track the minimum number of deletions needed.
Here's a step-by-step explanation of the algorithm used in the solution:
-
Initialize two variables:
b
to keep track of the number of 'b' characters encountered andans
to hold the minimum number of deletions required so far. Both are set to 0 at the start. -
Iterate over each character
c
in the strings
:- If
c
is 'b', increment the count ofb
since it might need to be deleted later if an 'a' follows. - If
c
is 'a', we have a decision to make. We can either delete this 'a' or all the 'b's we have encountered before. To make an optimal choice, we updateans
to be the minimum ofans + 1
(which represents deleting this 'a') andb
(which represents deleting all the 'b's encountered so far).
- If
-
The
min
function ensures that we choose the best possible outcome at each step, whether it's deleting the current 'a' or the 'b's counted previously. -
Upon completion of the iteration through the string,
ans
will hold the minimum number of deletions needed to make the string balanced.
This algorithm is efficient because it only goes through the string once, resulting in a time complexity of O(n)
, where n
is the length of the string. No additional data structures are used, and only constant extra space is required, making the space complexity O(1)
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider the string s = "bbaba"
. We will use the solution approach to determine the minimum number of deletions required to make this string balanced.
-
Initialize
b = 0
andans = 0
. No characters have been processed, so no deletions are necessary yet. -
Process the first character (from left to right):
c = 'b'
ā Incrementb
to1
. We may need to delete this 'b' later if an 'a' appears.- As it stands,
b = 1
andans = 0
.
-
Process the second character:
c = 'b'
ā Incrementb
to2
. So far, we have not seen an 'a', so no decision needs to be made.b = 2
andans = 0
.
-
Process the third character:
c = 'a'
ā We have a choice: delete this 'a' or delete the two 'b's encountered before. We choose the option that requires the least deletions.ans = min(ans + 1, b) = min(1, 2) = 1
. We decide to delete this 'a' as it involves fewer deletions.b = 2
andans = 1
.
-
Process the fourth character:
c = 'b'
ā Incrementb
to3
because we may need to delete this 'b' too if another 'a' appears.- Keep
b = 3
andans = 1
.
-
Process the fifth (and last) character:
c = 'a'
ā Again, we must decide whether to delete this 'a' or all previous 'b's. Again, choose the option with fewer deletions.ans = min(ans + 1, b) = min(2, 3) = 2
. We delete this 'a'.- Final
b = 3
andans = 2
.
Given the example string bbaba
, the minimum number of deletions required to balance the string, by the solution approach, is 2
. We delete the two 'a's encountered to prevent any 'b' from being followed by an 'a' later in the string.
Solution Implementation
1class Solution:
2 def minimumDeletions(self, s: str) -> int:
3 # Initialize the answer to 0 and a counter for 'b' characters
4 minimum_deletions = 0
5 count_b = 0
6
7 # Loop through each character in the string
8 for char in s:
9 if char == 'b':
10 # If the current character is 'b', increment the 'b' counter
11 count_b += 1
12 else:
13 # If the current character is 'a', compute the minimum of:
14 # 1. Current minimum deletions + 1 (assuming deleting current 'a')
15 # 2. Number of 'b' characters encountered so far
16 # This step ensures we take the minimum deletions needed to keep the string without 'ba' substring
17 minimum_deletions = min(minimum_deletions + 1, count_b)
18
19 # Return the computed minimum deletions
20 return minimum_deletions
21
1class Solution {
2 // Method to calculate the minimum number of deletions to make string 's' sorted
3 public int minimumDeletions(String s) {
4 int length = s.length(); // Store the length of the string 's'
5 int minDeletions = 0; // Initialize the minimum number of deletions to 0
6 int countB = 0; // Initialize the count of 'b' characters to 0
7
8 // Loop through every character in the string
9 for (int i = 0; i < length; ++i) {
10 // Check if the current character is 'b'
11 if (s.charAt(i) == 'b') {
12 // Increment the count of 'b' characters
13 ++countB;
14 } else {
15 // It's an 'a' so compute the minimum between
16 // deleting the current 'a' plus any previous minimum deletions
17 // and the count of 'b' characters seen so far
18 minDeletions = Math.min(minDeletions + 1, countB);
19 }
20 }
21 // Return the computed minimum number of deletions
22 return minDeletions;
23 }
24}
25
1class Solution {
2public:
3 int minimumDeletions(string s) {
4 int deletionsRequired = 0; // Tracks the number of deletions required
5 int countB = 0; // Counts the number of 'b's encountered
6
7 // Iterate over each character in the string
8 for (char& c : s) {
9 if (c == 'b') {
10 // When a 'b' is found, increment the count of 'b's
11 ++countB;
12 } else {
13 // If we encounter an 'a', decide whether to delete this 'a' or
14 // any 'b' encountered so far to get a sorted string 'aa...bb...'
15 // The min function chooses the smaller of deletion an 'a' or any previous 'b'
16 deletionsRequired = std::min(deletionsRequired + 1, countB);
17 }
18 }
19
20 // Return the minimum number of deletions required to sort the string
21 return deletionsRequired;
22 }
23};
24
1function minimumDeletions(s: string): number {
2 const stringLength = s.length; // Length of the input string
3 let deletionCount = 0, // Tracks the minimum number of deletions needed
4 countB = 0; // Counts the number of 'b' characters encountered
5
6 for (let i = 0; i < stringLength; ++i) {
7 if (s.charAt(i) === 'b') {
8 // If the current character is a 'b', increment the 'b' count
9 ++countB;
10 } else {
11 // If the current character is 'a', calculate the minimum between:
12 // 1. Incrementing the deletion count (as if deleting the 'a')
13 // 2. The current count of 'b's (indicating deletion of all 'b's encountered so far)
14 deletionCount = Math.min(deletionCount + 1, countB);
15 }
16 }
17
18 // Return the minimum number of deletions found
19 return deletionCount;
20}
21
Time and Space Complexity
The given Python code defines a function minimumDeletions
which takes a string s
and returns the minimum number of deletions required to make the string good. A string is considered good if there are no instances of 'b' that come after an 'a'. The algorithm uses two variables ans
and b
to track the minimum deletions required and the count of 'b's encountered respectively. It iterates through the string a single time and, therefore, has a linear relationship regarding the number of elements (characters in this case) in the input string.
Time Complexity
The time complexity of the function is O(n)
, where n
is the length of the input string s
. This is because the algorithm iterates through each character in the string exactly once.
Space Complexity
The space complexity of the function is O(1)
. It only uses a fixed number of variables (ans
and b
), which do not grow with the input size, meaning the amount of space used remains constant regardless of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!