Leetcode 1653: Minimum Deletions to Make String Balanced

Input: The input is a string s, consisting only of the characters 'a' and 'b'.

Example: s = "abbbba"

Constraints:

• 1 <= s.length <= 10^5

• Each character in s is either 'a' or 'b'.

Output: The output is an integer representing the minimum number of deletions required to make the string balanced.

Example: Output: 2

Constraints:

Goal: The goal is to minimize the number of deletions required to make the string balanced.

Steps:

• Iterate through the string and track the number of 'b' characters.

• For each 'a' encountered, determine the minimum deletions by comparing the current state with the previous state where 'b' characters are deleted.

• Return the minimum deletions found.

Goal: The solution must handle large strings efficiently, with length up to 100,000.

Steps:

• 1 <= s.length <= 10^5

• Each character in s is either 'a' or 'b'.

Assumptions:

• The string will always contain valid characters 'a' and 'b'.

• Input: s = "abbbba"

• Explanation: We need to ensure that no 'b' appears before 'a'. By deleting the minimum number of characters, we can balance the string.

Approach: The approach involves tracking the number of 'b' characters and minimizing deletions based on the appearance of 'a' characters.

Observations:

• We need to carefully handle 'b' characters and count the necessary deletions to make the string balanced.

• This problem can be solved by using dynamic programming to track the minimum deletions required for each position in the string.

Steps:

• Initialize a variable to track the count of 'b' characters.

• Create a DP array where each position represents the minimum deletions required up to that point.

• Iterate through the string, updating the DP array based on whether the character is 'a' or 'b'.

• Return the value of the DP array for the last position.

Empty Inputs:

• Consider the case where the string has only one character.

Large Inputs:

• Ensure that the solution works efficiently with strings of length up to 100,000.

Special Values:

• Handle cases where the string is already balanced, such as a string with only 'a's or only 'b's.

Constraints:

• The solution must handle both small and large input sizes efficiently.

int minimumDeletions(string s) {
    int n = s.size(), bcnt = 0;
    vector<int> dp(n + 1, 0);
    for(int i = 0; i < n; i++) {
        char a = s[i];
        if(a == 'a') {                
            dp[i + 1] = min(dp[i] + 1, bcnt);
        } else {
            bcnt++;
            dp[i + 1] = dp[i];
        }
    }
    return dp[n];
}

1 : Function Declaration

int minimumDeletions(string s) {

Defines the function that calculates the minimum deletions needed to make the string valid.

2 : Variable Initialization

    int n = s.size(), bcnt = 0;

Initializes the string size and a counter for the number of 'b's encountered.

3 : Array Initialization

    vector<int> dp(n + 1, 0);

Creates a dynamic programming array to store intermediate results.

4 : Loop

    for(int i = 0; i < n; i++) {

Iterates through each character in the string.

5 : Variable Initialization

        char a = s[i];

Stores the current character for processing.

6 : Conditional Statement

        if(a == 'a') {

Checks if the current character is 'a'.

7 : Dynamic Programming

            dp[i + 1] = min(dp[i] + 1, bcnt);

Updates the dp array for 'a' by choosing the minimum deletions needed.

8 : Conditional Statement

        } else {

Handles the case where the current character is 'b'.

9 : Counter Increment

            bcnt++;

Increments the count of 'b' characters encountered.

10 : Dynamic Programming

            dp[i + 1] = dp[i];

Carries forward the dp value for 'b', as no deletion is required.

11 : Return Statement

    return dp[n];

Returns the minimum deletions needed to make the string valid.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the length of the string, since we iterate through the string once.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) due to the dynamic programming array used to store the minimum deletions at each step.

Leetcode 1653: Minimum Deletions to Make String Balanced

Explore →