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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Deletions to Make String Balanced

Number: 1756

Difficulty: Medium

Paid? No

Companies: Google, Microsoft, redbus

Problem Description

Given a string s consisting only of characters 'a' and 'b', determine the minimum number of deletions needed to make s balanced. A string is balanced if there is no pair of indices (i, j) where i < j with s[i] = 'b' and s[j] = 'a'. Essentially, all 'a's should appear before any 'b's in the final string.

Key Insights

  • A balanced string means every 'a' must come before every 'b'.
  • When scanning the string, conflicts occur when an 'a' appears after a 'b'.
  • At each 'a', we face a choice: delete the current 'a' or delete all preceding 'b's.
  • By maintaining a counter for 'b's and tracking the minimum deletions required so far, we can decide optimally at each step.
  • This approach leverages a greedy/dynamic programming method with a single pass.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string. Space Complexity: O(1) since only a few variables are used.

Solution

The solution iterates through the string while keeping track of two variables: countB (the number of 'b's encountered so far) and deletionCount (the minimum deletions required up to the current point). For each character:

  • If the character is 'b', increment countB.
  • If the character is 'a', update deletionCount to be the minimum of either deleting this 'a' (deletionCount + 1) or deleting all previous 'b's (which is countB). This strategy ensures that the final deletionCount reflects the minimum number of deletions needed to achieve a balanced string.

Code Solutions

# Function to compute minimum deletions needed to make a string balanced
def minimum_deletions(s):
    deletion_count = 0  # Tracks the minimum number of deletions required so far
    count_b = 0       # Counts the number of 'b' characters encountered
    # Iterate over each character in the string
    for char in s:
        if char == 'b':
            count_b += 1  # Increment count for each 'b'
        else:  # char is 'a'
            # Either delete the current 'a' (deletion_count + 1) or remove all previous 'b's (count_b)
            deletion_count = min(deletion_count + 1, count_b)
    return deletion_count

# Example usage
s = "aababbab"
print(minimum_deletions(s))  # Expected output: 2
← Back to All Questions