D
DevExCode

LeetCode 1653: Minimum Deletions to Make String Balanced Solution

Master LeetCode problem 1653 (Minimum Deletions to Make String Balanced), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1653. Minimum Deletions to Make String Balanced

Medium
StringDynamic ProgrammingStack

Problem Explanation

Explanation:

To make the string balanced, we need to delete characters such that there are no occurrences of "ba" in the string. We can achieve this by iterating through the string and keeping track of the number of 'a's encountered so far. Whenever we encounter a 'b', we have two choices: either delete the 'b' or delete the last 'a' encountered. We choose the option that minimizes the number of deletions needed.

Algorithm:

  1. Initialize a variable aCount to keep track of the number of 'a's encountered so far.
  2. Initialize a variable deletions to 0 to keep track of the number of deletions needed.
  3. Iterate through the string:
    • If the current character is 'a', increment aCount.
    • If the current character is 'b':
      • If there are 'a's encountered before, decrement aCount and increment deletions.
      • If there are no 'a's encountered before, increment deletions.
  4. Return the final value of deletions.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the length of the input string s.

Space Complexity:

The space complexity of this algorithm is O(1) as we are using a constant amount of extra space.

:

Solution Code

class Solution {
    public int minimumDeletions(String s) {
        int aCount = 0;
        int deletions = 0;
        
        for (char c : s.toCharArray()) {
            if (c == 'a') {
                aCount++;
            } else {
                if (aCount > 0) {
                    aCount--;
                } else {
                    deletions++;
                }
            }
        }
        
        return deletions;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1653 (Minimum Deletions to Make String Balanced)?

This page provides optimized solutions for LeetCode problem 1653 (Minimum Deletions to Make String Balanced) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1653 (Minimum Deletions to Make String Balanced)?

The time complexity for LeetCode 1653 (Minimum Deletions to Make String Balanced) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1653 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1653 in Java, C++, or Python.

Back to LeetCode Solutions