LeetCode 2696: Minimum String Length After Removing Substrings

Stack

Here “AB” is like “()” and “CD” is like “{}”. Deleting a pair enables further deletes if they are nested with matching open and close like: (()), {()}, {{}}, ({}). For example: “ACDB”. So, we use a stack to simulate deletes.

Time: $\mathcal{O}(n)$ , space: same.

class Solution:
    def minLength(self, s: str) -> int:
        pair_of = defaultdict(str, {"B": "A", "D": "C"})
        stack = []
        for c in s:
            if stack and pair_of[c] == stack[-1]:
                stack.pop()
            else:
                stack.append(c)

        return len(stack)

Two pointers

If we could modify the string, s, in-place, we could get away with $\mathcal{O}(1)$ space.

Our string is punctured by regions with nested deletable pairs like below. After deletes, we want all not-deletable regions next to each other.

With two pointers i and j, we can do that consolidation. The left pointer, i, will always mark the end of the consolidated not-deletable region. So, in the end, the length after deletes is (i+1).

If (i, j) is a not-deletable pair, we copy s[j] into s[i+1] extending the consolidated not-deletable region.

class Solution:
    def is_deletable_pair(self, i, j, s) -> bool:
        if i < 0:
            return False
        return (s[i] == "A" and s[j] == "B") or (s[i] == "C" and s[j] == "D")

    def minLength(self, s: str) -> int:
        s = list(s)

        i = -1
        for j in range(len(s)):
            if self.is_deletable_pair(i, j, s):
                i -= 1
            else:
                i += 1
                s[i] = s[j]

        return i+1

unreasonably effective