Introduction

In this blog post, we will explore how to solve the LeetCode problem "1653" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. Example 1: Input: s = "aababbab" Output: 2 Explanation: You can either: Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb"). Example 2: Input: s = "bbaaaaabb" Output: 2 Explanation: The only solution is to delete the first two characters. Constraints: 1 <= s.length <= 105 s[i] is 'a' or 'b'​​.

Explanation

Here's the breakdown of the approach and the Python code:

• High-Level Approach:

  • Iterate through the string, maintaining a count of 'a's encountered so far.
  • For each 'b' encountered, we have a choice: either delete the 'b' or delete all the 'a's seen before it. We choose the option that results in fewer deletions.
  • The minimum number of deletions needed will be the result.

• Complexity:

  • Runtime Complexity: O(n)
  • Storage Complexity: O(1)

Code

    def minDeletions(s: str) -> int:
    """
    Calculates the minimum number of deletions needed to make a string balanced.

    Args:
        s: The input string consisting of 'a' and 'b' characters.

    Returns:
        The minimum number of deletions needed to make the string balanced.
    """

    a_count = 0
    deletions = 0

    for char in s:
        if char == 'a':
            a_count += 1
        else:  # char == 'b'
            deletions = min(deletions + 1, a_count)

    return deletions