Minimum String Length After Removing Substrings

Minimum String Length After Removing Substrings - 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.

Input & Output

Example 1 — Multiple Removals

$ Input: s = "ABFCACDB"

› Output: 2

💡 Note: Remove "AB" → "FCACDB", then remove "CD" → "FCAB", then remove "AB" → "FC". Final length is 2.

Example 2 — Complete Removal

$ Input: s = "ACBDCD"

› Output: 0

💡 Note: Remove "CD" → "ACBD", then remove "AB" → "CD", then remove "CD" → "". Final length is 0.

Example 3 — No Removals Possible

$ Input: s = "ACBD"

› Output: 4

💡 Note: No "AB" or "CD" substrings exist, so no operations can be performed. Final length is 4.

Constraints

1 ≤ s.length ≤ 100
s consists only of uppercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input String

Original string with removable patterns

Remove Patterns

AB and CD substrings are eliminated

Final Length

Count remaining characters

Key Takeaway

🎯 Key Insight: Use stack-like processing to immediately remove patterns as they form, avoiding multiple string scans

Asked in

f Meta 15 a Amazon 12 M Microsoft 8 Apple 6

The key insight is to recognize this as a pattern matching problem similar to balanced parentheses. Best approach uses a stack simulation to process characters in one pass, removing AB/CD patterns immediately when they form. Time: O(n), Space: O(1) with in-place simulation.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Repeated String Replacement	O(n²)	O(n)	Repeatedly search for "AB" or "CD" and remove them until no more can be found
Stack-Based Simulation	O(n)	O(n)	Use stack to simulate the removal process efficiently in one pass
In-Place Character Array Simulation	O(n)	O(1)	Simulate stack behavior using the input string as character array for O(1) space

Brute Force - Repeated String Replacement — Algorithm Steps

Scan string for "AB" or "CD"
Remove first occurrence found
Repeat until no more patterns exist
Return final string length

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Pattern

Scan string for AB or CD

Remove

Remove first occurrence found

Repeat

Continue until no patterns remain

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int solution(char* s) {
    int len = strlen(s);
    char* pos;
    
    while ((pos = strstr(s, "AB")) != NULL || (pos = strstr(s, "CD")) != NULL) {
        if (strstr(s, "AB") != NULL) {
            pos = strstr(s, "AB");
        } else {
            pos = strstr(s, "CD");
        }
        memmove(pos, pos + 2, strlen(pos + 2) + 1);
        len -= 2;
    }
    return len;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

In worst case, we remove one character pair per iteration and scan entire string each time

⚠ Quadratic Growth

Space Complexity

O(n)

String operations may create new string objects during replacement

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Repeated String Replacement — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler