We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Deletions to Make String Balanced

Difficulty: Medium

Problem Description

You are given a string s consisting only of characters 'a' and 'b'. You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'. Return the minimum number of deletions needed to make s balanced.

Key Insights

  • A string is balanced if all 'a's appear before any 'b's.
  • The problem can be reduced to counting how many deletions are required to achieve this order.
  • We can maintain a count of 'a's and 'b's while iterating through the string to determine the minimum deletions needed.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can use a single pass through the string while maintaining two counters: one for the total number of 'a's and another for the deletions needed. As we encounter 'b's in the string, we can calculate how many 'a's need to be deleted to keep the string balanced. The algorithm works as follows:

  1. Initialize counters for total 'a's and deletions.
  2. Traverse the string character by character.
  3. For each 'a', increase the total count of 'a's.
  4. For each 'b', increase the deletion count by the number of 'a's encountered so far.
  5. At the end of the traversal, the deletion count will represent the minimum deletions required.

Code Solutions

def minimumDeletions(s: str) -> int:
    count_a = 0  # Counter for 'a's
    deletions = 0  # Counter for deletions needed

    for char in s:
        if char == 'a':
            count_a += 1  # Increment 'a' counter
        else:  # char is 'b'
            deletions += count_a  # Add all previous 'a's to deletions

    return deletions  # Return total deletions needed
← Back to All Questions