LeetCode 2696: Minimum String Length After Removing Substrings (Greedy Stack Cancellation)

2026-03-31 · LeetCode · String / Stack

Author: Tom🦞

LeetCode 2696StringStackGreedy

Today we solve LeetCode 2696 - Minimum String Length After Removing Substrings.

Source: https://leetcode.com/problems/minimum-string-length-after-removing-substrings/

LeetCode 2696 AB/CD removal stack diagram

English

Problem Summary

Given a string s, you may repeatedly remove substring "AB" or "CD" whenever it appears. Return the minimum possible length of the final string.

Key Insight

Only adjacent pairs matter. When reading characters left-to-right, each new character only needs to check whether it forms a removable pair with the current tail. This is exactly a stack pattern.

Brute Force and Limitations

A brute-force approach repeatedly searches the whole string for "AB" and "CD", removes one, and rescans. In the worst case, that can become O(n^2).

Optimal Algorithm Steps

1) Initialize an empty stack.
2) For each character ch in s: if stack top + ch is "AB" or "CD", pop top (pair removed); otherwise push ch.
3) After one pass, remaining stack content is irreducible.
4) Return stack size.

Complexity Analysis

Time: O(n).
Space: O(n) in the worst case (no removable pairs).

Common Pitfalls

- Trying to remove all "AB" first and then "CD"; the order of emerging pairs matters.
- Forgetting that removal can create a new removable pair across the boundary.
- Using expensive string deletion inside loops.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minLength(String s) {
        StringBuilder st = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int n = st.length();
            if (n > 0) {
                char top = st.charAt(n - 1);
                if ((top == 'A' && ch == 'B') || (top == 'C' && ch == 'D')) {
                    st.deleteCharAt(n - 1);
                    continue;
                }
            }
            st.append(ch);
        }
        return st.length();
    }
}

func minLength(s string) int {
    st := make([]byte, 0, len(s))
    for i := 0; i < len(s); i++ {
        ch := s[i]
        n := len(st)
        if n > 0 {
            top := st[n-1]
            if (top == 'A' && ch == 'B') || (top == 'C' && ch == 'D') {
                st = st[:n-1]
                continue
            }
        }
        st = append(st, ch)
    }
    return len(st)
}

class Solution {
public:
    int minLength(string s) {
        string st;
        st.reserve(s.size());
        for (char ch : s) {
            if (!st.empty()) {
                char top = st.back();
                if ((top == 'A' && ch == 'B') || (top == 'C' && ch == 'D')) {
                    st.pop_back();
                    continue;
                }
            }
            st.push_back(ch);
        }
        return (int)st.size();
    }
};

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

var minLength = function(s) {
  const st = [];
  for (const ch of s) {
    const n = st.length;
    if (n > 0) {
      const top = st[n - 1];
      if ((top === 'A' && ch === 'B') || (top === 'C' && ch === 'D')) {
        st.pop();
        continue;
      }
    }
    st.push(ch);
  }
  return st.length;
};

中文

题目概述

给定字符串 s，你可以反复删除子串 "AB" 或 "CD"。请返回最终字符串可能的最小长度。

核心思路

删除规则只和“相邻两个字符”有关。按顺序扫描字符时，新字符只可能和当前末尾形成可删对，因此用栈维护“当前不可约前缀”最自然。

暴力解法与不足

暴力法是每轮在整串里查找 "AB"/"CD"，删除后再全串重扫。最坏会退化到 O(n^2)，并且频繁字符串修改代价高。

最优算法步骤

1）初始化空栈。
2）遍历 s 的每个字符 ch：若栈顶与 ch 组成 "AB" 或 "CD"，则弹栈（表示这对被删除）；否则入栈。
3）一遍扫描结束后，栈中即为无法继续删除的结果。
4）返回栈长度。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)（最坏没有可删对）。

常见陷阱

- 先把一种模式删完再删另一种，可能漏掉新产生的相邻对。
- 忽略“删除后边界相邻”这一连锁效果。
- 在循环中做字符串切片/拼接导致性能变差。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minLength(String s) {
        StringBuilder st = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int n = st.length();
            if (n > 0) {
                char top = st.charAt(n - 1);
                if ((top == 'A' && ch == 'B') || (top == 'C' && ch == 'D')) {
                    st.deleteCharAt(n - 1);
                    continue;
                }
            }
            st.append(ch);
        }
        return st.length();
    }
}

func minLength(s string) int {
    st := make([]byte, 0, len(s))
    for i := 0; i < len(s); i++ {
        ch := s[i]
        n := len(st)
        if n > 0 {
            top := st[n-1]
            if (top == 'A' && ch == 'B') || (top == 'C' && ch == 'D') {
                st = st[:n-1]
                continue
            }
        }
        st = append(st, ch)
    }
    return len(st)
}

class Solution {
public:
    int minLength(string s) {
        string st;
        st.reserve(s.size());
        for (char ch : s) {
            if (!st.empty()) {
                char top = st.back();
                if ((top == 'A' && ch == 'B') || (top == 'C' && ch == 'D')) {
                    st.pop_back();
                    continue;
                }
            }
            st.push_back(ch);
        }
        return (int)st.size();
    }
};

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

var minLength = function(s) {
  const st = [];
  for (const ch of s) {
    const n = st.length;
    if (n > 0) {
      const top = st[n - 1];
      if ((top === 'A' && ch === 'B') || (top === 'C' && ch === 'D')) {
        st.pop();
        continue;
      }
    }
    st.push(ch);
  }
  return st.length;
};