Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Minimum String Length After Removing Substrings solution and explanation

EasySimulationStackString6 min read77.0% acceptanceUpdated 9 Apr 2026
Asked atWells FargoIBMBoltGoogleAmazonMeta
Practise Minimum String Length After Removing Substrings
11:47
Minimum String Length After Removing Substrings - Leetcode 2696 - PythonNeetCodeIO · 11:47 · 7K viewsWatch on YouTube
9 more videos on this problem
  1. Minimum String Length After Removing Substrings - Leetcode 2696 - PythonNeetCodeIO · 11:47 · 7K views
  2. LeetCode 2696. Minimum String Length After Removing Substrings - Interview Prep Ep 141Fisher Coder · 7:45 · 1K views
  3. Minimum String Length After Removing Substrings | Leetcode 2696Techdose · 12:41 · 1K views
  4. Minimum String Length After Removing Substrings - Leetcode 2696 - PythonAlgorithms Casts · 6:08 · 543 views
  5. 2696. Minimum String Length After Removing Substrings (Leetcode Easy)Programming Live with Larry · 2:45 · 272 views
  6. Minimum String Length After Removing Substrings| Leetcode 2696| leetcode daily problem today |StringCode Thoughts · 12:17 · 251 views
  7. MINIMUM STRING LENGTH AFTER REMOVING SUBSTRINGS | LEETCODE 2696 | PYTHON SOLUTIONCracking FAANG · 4:59 · 209 views
  8. Leetcode 2696. Minimum String Length After Removing SubstringsElite Code · 21:55 · 180 views
  9. Minimum String Length After Removing Substrings - Leetcode 2696 - JavaCode With K5KC · 10:38 · 71 views
  10. Leetcode Daily #2696 : Minimum String Length After Removing Substrings in C++DANIELSMS · 3:35 · 63 views

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.

Return the minimum possible length of the resulting string that you can obtain.

Note that the string concatenates after removing the substring and could produce new "AB" or "CD" substrings.

Example 1:

Input: s = "ABFCACDB"
Output: 2
Explanation: We can do the following operations:
- Remove the substring "ABFCACDB", so s = "FCACDB".
- Remove the substring "FCACDB", so s = "FCAB".
- Remove the substring "FCAB", so s = "FC".
So the resulting length of the string is 2.
It can be shown that it is the minimum length that we can obtain.

Example 2:

Input: s = "ACBBD"
Output: 5
Explanation: We cannot do any operations on the string so the length remains the same.

Constraints:

  • 1 <= s.length <= 100
  • s consists only of uppercase English letters.

Approach overview

Problem Overview: You receive a string containing uppercase letters. You can repeatedly remove the substrings "AB" and "CD". Each removal shortens the string and may create new removable pairs. The goal is to return the minimum possible length after no more valid substrings remain.

Approach 1: Stack-Based Simulation (O(n) time, O(n) space)

This approach treats the problem as a streaming removal process using a stack. Iterate through the string character by character. For each character, check the top of the stack. If the top forms "AB" or "CD" with the current character, pop the stack instead of pushing the new character. This simulates removing the substring immediately. Otherwise, push the current character onto the stack.

The key insight: every valid removal only depends on the most recent character that remains in the string. A stack naturally models this behavior. Each character is pushed and popped at most once, giving O(n) time complexity with O(n) auxiliary space. This approach is straightforward and mirrors the exact removal process described in the problem.

Approach 2: Two-Pointer Iterative Method (O(n) time, O(1) extra space)

You can simulate the same behavior using a write pointer instead of an explicit stack. Convert the string into a mutable array and maintain a pointer that represents the current "stack top". Iterate through the characters with a second pointer. If the current character together with the previous written character forms "AB" or "CD", move the write pointer back (effectively deleting the pair). Otherwise, write the character and move the pointer forward.

This technique behaves like a stack but stores results directly inside the original array. Because the algorithm only moves pointers and overwrites characters, the extra memory usage drops to O(1). Time complexity remains O(n) since each character is processed once. This is a common pattern in two pointer and simulation problems where the result can be built in-place.

Recommended for interviews: The stack-based approach is the most intuitive and is typically what interviewers expect first. It clearly demonstrates how you model repeated removals using a data structure. The two-pointer variant shows deeper optimization skills by eliminating the extra stack and performing the same logic in-place while maintaining O(n) time.

Approach 1: Stack-Based Approach

This approach revolves around using a stack to efficiently identify and remove the substrings "AB" and "CD" from the given string. By traversing each character of the string:

  • If the current character and the top of the stack form "AB" or "CD", pop from the stack as they form a pattern to remove.
  • If not, push the current character onto the stack. This keeps future potential patterns intact until further examination.

The characters that remain on the stack are the ones that could not form any removable patterns, thus forming the result string.

def minLengthAfterRemovals(s):
    stack = []
    for char in s:
        if stack and ((char == 'B' and stack[-1] == 'A') or (char == 'D' and stack[-1] == 'C')):
            stack.pop()
        else:
            stack.append(char)
    return len(stack)

s = "ABFCACDB"
print(minLengthAfterRemovals(s))
import java.util.Stack;

public class MinLength {
    public static int minLengthAfterRemovals(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && ((c == 'B' && stack.peek() == 'A') || (c == 'D' && stack.peek() == 'C'))) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.size();
    }

    public static void main(String[] args) {
        String s = "ABFCACDB";
        System.out.println(minLengthAfterRemovals(s));
    }
}
#include <iostream>
#include <stack>
using namespace std;

int minLengthAfterRemovals(string s) {
    stack<char> st;
    for (char c : s) {
        if (!st.empty() && ((c == 'B' && st.top() == 'A') || (c == 'D' && st.top() == 'C'))) {
            st.pop();
        } else {
            st.push(c);
        }
    }
    return st.size();
}

int main() {
    string s = "ABFCACDB";
    cout << minLengthAfterRemovals(s) << endl;
    return 0;
}
function minLengthAfterRemovals(s) {
    let stack = [];
    for (let char of s) {
        if (stack.length > 0 && ((char === 'B' && stack[stack.length - 1] === 'A') || (char === 'D' && stack[stack.length - 1] === 'C'))) {
            stack.pop();
        } else {
            stack.push(char);
        }
    }
    return stack.length;
}

const s = "ABFCACDB";
console.log(minLengthAfterRemovals(s));
#include <stdio.h>
#include <string.h>

int minLengthAfterRemovals(const char *s) {
    char stack[100];
    int top = -1;
    for (int i = 0; s[i]; ++i) {
        if (top != -1 && ((s[i] == 'B' && stack[top] == 'A') || (s[i] == 'D' && stack[top] == 'C'))) {
            --top; // Pop the stack
        } else {
            stack[++top] = s[i]; // Push onto stack
        }
    }
    return top + 1; // The resulting length
}

int main() {
    const char *s = "ABFCACDB";
    printf("%d\n", minLengthAfterRemovals(s));
    return 0;
}
using System;
using System.Collections.Generic;

public class MinLengthString {
    public static int MinLengthAfterRemovals(string s) {
        Stack<char> stack = new Stack<char>();
        foreach (char c in s) {
            if (stack.Count > 0 && ((c == 'B' && stack.Peek() == 'A') || (c == 'D' && stack.Peek() == 'C'))) {
                stack.Pop();
            } else {
                stack.Push(c);
            }
        }
        return stack.Count;
    }
    
    public static void Main(string[] args) {
        string s = "ABFCACDB";
        Console.WriteLine(MinLengthAfterRemovals(s));
    }
}

This Python implementation uses a list to serve as a stack, taking advantage of Python's list pop and append to simulate stack operations effectively.

Complexity

Time Complexity: O(n), linear in terms of input size.
Space Complexity: O(n), bounded by the stack's space usage.

Try this approach in the editor

Approach 2: Two-Pointer Iterative Method

This technique uses a two-pointer approach to reduce the string by altering it in place. The core idea is to selectively overwrite positions in the string:

  • Incrementally check pairs of characters: if they comprise a known removable substring, skip them both.
  • If not, replace the write pointer's position with the read character, then advance the write position after adjustments.

After reaching the end of the string, the length of the string from the start to the write pointer represents the reduced string length.

def minLengthAfterRemovals(s):
    s = list(s)
    write = 0
    for read in range(len(s)):
        if write > 0 and ((s[read] == 'B' and s[write - 1] == 'A') or (s[read] == 'D' and s[write - 1] == 'C')):
            write -= 1
        else:
            s[write] = s[read]
            write += 1
    return write

s = "ABFCACDB"
print(minLengthAfterRemovals(s))
public class MinLength {
    public static int minLengthAfterRemovals(String s) {
        char[] arr = s.toCharArray();
        int write = 0;
        for (int read = 0; read < s.length(); read++) {
            if (write > 0 && ((arr[read] == 'B' && arr[write - 1] == 'A') || (arr[read] == 'D' && arr[write - 1] == 'C'))) {
                write--;
            } else {
                arr[write++] = arr[read];
            }
        }
        return write;
    }

    public static void main(String[] args) {
        String s = "ABFCACDB";
        System.out.println(minLengthAfterRemovals(s));
    }
}
#include <iostream>
#include <string>
using namespace std;

int minLengthAfterRemovals(string &s) {
    int write = 0;
    for (int read = 0; read < s.size(); ++read) {
        if (write > 0 && ((s[read] == 'B' && s[write - 1] == 'A') || (s[read] == 'D' && s[write - 1] == 'C'))) {
            --write;
        } else {
            s[write++] = s[read];
        }
    }
    return write;
}

int main() {
    string s = "ABFCACDB";
    cout << minLengthAfterRemovals(s) << endl;
    return 0;
}
function minLengthAfterRemovals(s) {
    let arr = s.split(''); // Convert string to array for direct manipulation
    let write = 0;
    for (let read = 0; read < arr.length; read++) {
        if (write > 0 && ((arr[read] === 'B' && arr[write - 1] === 'A') || (arr[read] === 'D' && arr[write - 1] === 'C'))) {
            write--;
        } else {
            arr[write++] = arr[read];
        }
    }
    return write;
}

const s = "ABFCACDB";
console.log(minLengthAfterRemovals(s));
#include <stdio.h>
#include <string.h>

int minLengthAfterRemovals(char *s) {
    int n = strlen(s);
    int write = 0;
    for (int read = 0; read < n; ++read) {
        if (write && ((s[read] == 'B' && s[write - 1] == 'A') || (s[read] == 'D' && s[write - 1] == 'C'))) {
            --write;
        } else {
            s[write++] = s[read];
        }
    }
    return write;
}

int main() {
    char s[] = "ABFCACDB";
    printf("%d\n", minLengthAfterRemovals(s));
    return 0;
}
using System;

public class MinLengthString {
    public static int MinLengthAfterRemovals(string s) {
        char[] arr = s.ToCharArray();
        int write = 0;
        for (int read = 0; read < arr.Length; read++) {
            if (write > 0 && ((arr[read] == 'B' && arr[write - 1] == 'A') || (arr[read] == 'D' && arr[write - 1] == 'C'))) {
                write--;
            } else {
                arr[write++] = arr[read];
            }
        }
        return write;
    }
    
    public static void Main(string[] args) {
        string s = "ABFCACDB";
        Console.WriteLine(MinLengthAfterRemovals(s));
    }
}

In Python, the string is transformed into a mutable list of characters. Using two indices, characters are compared and overwritten as needed, ensuring patterns are skipped and not translated into the resulting sequence.

Complexity

Time Complexity: O(n), requires inspection of each character.
Space Complexity: O(1), achieved by manipulating the original list.

Try this approach in the editor

Approach 3: Stack

We traverse the string s. For the current character c we are traversing, if the stack is not empty and the top element of the stack top can form AB or CD with c, then we pop the top element of the stack, otherwise we push c into the stack.

The number of remaining elements in the stack is the length of the final string.

In implementation, we can pre-place an empty character in the stack, so there is no need to judge whether the stack is empty when traversing the string. Finally, we can return the size of the stack minus one.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.

function minLength(s: string): number {
    const stk: string[] = [];
    for (const c of s) {
        if ((stk.at(-1) === 'A' && c === 'B') || (stk.at(-1) === 'C' && c === 'D')) {
            stk.pop();
        } else {
            stk.push(c);
        }
    }
    return stk.length;
}
func minLength(s string) int {
	stk := []byte{' '}
	for _, c := range s {
		if (c == 'B' && stk[len(stk)-1] == 'A') || (c == 'D' && stk[len(stk)-1] == 'C') {
			stk = stk[:len(stk)-1]
		} else {
			stk = append(stk, byte(c))
		}
	}
	return len(stk) - 1
}
impl Solution {
    pub fn min_length(s: String) -> i32 {
        let mut ans: Vec<u8> = Vec::new();

        for c in s.bytes() {
            if let Some(last) = ans.last() {
                if *last == b'A' && c == b'B' {
                    ans.pop();
                } else if *last == b'C' && c == b'D' {
                    ans.pop();
                } else {
                    ans.push(c);
                }
            } else {
                ans.push(c);
            }
        }

        ans.len() as i32
    }
}
Try this approach in the editor

Approach 4: One-liner

const minLength = (s: string, n = s.length): number =>
    ((s = s.replace(/AB|CD/g, '')), s.length === n) ? n : minLength(s);
Try this approach in the editor

Complexity comparison

ApproachComplexity
Stack-Based Approach

Time Complexity: O(n), linear in terms of input size.
Space Complexity: O(n), bounded by the stack's space usage.

Two-Pointer Iterative Method

Time Complexity: O(n), requires inspection of each character.
Space Complexity: O(1), achieved by manipulating the original list.

Stack–
One-liner–

Complexity analysis

ApproachTimeSpaceWhen to Use
Stack-Based SimulationO(n)O(n)Most intuitive solution; clearly models substring removals and is easy to implement during interviews
Two-Pointer Iterative MethodO(n)O(1)Preferred when minimizing memory usage or when modifying the string in-place

Frequently asked questions

Is Minimum String Length After Removing Substrings easy or hard?

Minimum String Length After Removing Substrings is classified as an Easy problem on LeetCode with a high acceptance rate around 77%. The main challenge is recognizing that repeated removals can be simulated with a stack, allowing the problem to be solved in linear time.

Minimum String Length After Removing Substrings Python/Java solution

In Python or Java, iterate through the string and maintain a stack (or StringBuilder acting as a stack). When the top element combined with the current character forms "AB" or "CD", remove the top element instead of adding the new character. The final stack size represents the minimum string length.

How to solve Minimum String Length After Removing Substrings in O(n)?

Scan the string once and simulate removals while building the result. Using a stack, check whether the top element plus the current character forms "AB" or "CD". If it does, pop the stack; otherwise push the character. Since each character is handled once, the algorithm runs in O(n) time.

What is the best approach for Minimum String Length After Removing Substrings?

The stack-based simulation is the most common approach. Traverse the string and push characters onto a stack unless the top of the stack forms "AB" or "CD" with the current character. When such a pair appears, pop the stack to simulate removal. This processes each character once, giving O(n) time and O(n) space.

Is Minimum String Length After Removing Substrings asked at Google/Amazon/Meta?

Problems involving stack-based string reduction and pair removal patterns commonly appear in interviews at companies like Amazon, Google, and Meta. The question tests understanding of stack simulation, string processing, and recognizing when only the most recent characters affect the result.

What data structure is used in Minimum String Length After Removing Substrings?

A stack is the primary data structure used in the standard solution. It allows efficient tracking of the most recent character so you can quickly check whether a removable pair like "AB" or "CD" is formed. The stack can also be simulated using a two-pointer technique on a character array.

What is the time complexity of Minimum String Length After Removing Substrings?

The optimal time complexity is O(n), where n is the length of the string. Each character is pushed and popped from the stack at most once, or processed once with the two-pointer method. Space complexity is O(n) with a stack or O(1) when using the in-place two-pointer technique.

Comments

Now write it yourselfClose this page and solve Minimum String Length After Removing Substrings in the editor, without looking.
Practise Minimum String Length After Removing Substrings