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:

  1. Initialize two variables: b to keep track of the number of 'b' characters encountered and ans to hold the minimum number of deletions required so far. Both are set to 0 at the start.

  2. Iterate over each character c in the string s:

    • If c is 'b', increment the count of b 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 update ans to be the minimum of ans + 1 (which represents deleting this 'a') and b (which represents deleting all the 'b's encountered so far).
  3. 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.

  4. 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 Evaluator

Example 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.

  1. Initialize b = 0 and ans = 0. No characters have been processed, so no deletions are necessary yet.

  2. Process the first character (from left to right):

    • c = 'b' ā†’ Increment b to 1. We may need to delete this 'b' later if an 'a' appears.
    • As it stands, b = 1 and ans = 0.
  3. Process the second character:

    • c = 'b' ā†’ Increment b to 2. So far, we have not seen an 'a', so no decision needs to be made.
    • b = 2 and ans = 0.
  4. 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 and ans = 1.
  5. Process the fourth character:

    • c = 'b' ā†’ Increment b to 3 because we may need to delete this 'b' too if another 'a' appears.
    • Keep b = 3 and ans = 1.
  6. 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 and ans = 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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

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

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More