Minimum String Length After Removing Substrings — LeetCode 2696 Python Solution

The problem

You are given a string s consisting only of uppercase English letters. You can apply some operations to this string where, in one operation, you can remove any occurrence of one of the substrings "AB" or "CD" from s.

Example

Input

s = "ABFCACDB"

Output

2

Explanation

We can do the following operations:

Python solution

class Solution:
    def minLength(self, s: str) -> int:
        stk = [""]
        for c in s:
            if (c == "B" and stk[-1] == "A") or (c == "D" and stk[-1] == "C"):
                stk.pop()
            else:
                stk.append(c)
        return len(stk) - 1

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 2696. Minimum String Length After Removing Substrings is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems