Scale Engineer

Minimum String Length After Removing Substrings

Easy
#2436Time: O(N^2), where N is the length of the string. The outer loop can run up to N/2 times, as we remove 2 characters in each successful iteration. Inside the loop, `indexOf` and `delete` on a `StringBuilder` can take up to O(N) time. Thus, the total time complexity is O(N * N) = O(N^2).Space: O(N), where N is the length of the string. This is required to store the `StringBuilder`.2 companies
Data structures
StringStack
Companies
J.P. MorganYelp

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the removal process directly. It repeatedly scans the string to find and remove occurrences of "AB" or "CD" until no more such substrings can be found. This process continues until the string's length stabilizes.

Algorithm

    1. Create a StringBuilder from the input string s for efficient modification.
    1. Enter a loop that continues as long as the string can be shortened. A flag or checking the length before and after a pass can be used to control the loop.
    1. Inside the loop, first search for an occurrence of the substring "AB".
    1. If "AB" is found, delete it from the StringBuilder and restart the search from the beginning of the modified string (e.g., by using continue in the loop).
    1. If "AB" is not found, search for an occurrence of "CD".
    1. If "CD" is found, delete it and restart the search.
    1. The loop terminates when a full pass is made without finding either "AB" or "CD".
    1. Return the length of the final StringBuilder.

Walkthrough

The algorithm works by entering a loop that continues as long as removals are possible. In each iteration, it searches for the substrings "AB" or "CD". If one is found, it's removed by modifying the string (or a StringBuilder for efficiency). The process is repeated on the new string. The loop terminates when a full pass over the string results in no removals. The length of the final string is the result.

For example, with s = "ABFCACDB":

    1. Find "AB" and remove it. s becomes "FCACDB".
    1. Find "CD" and remove it. s becomes "FCAB".
    1. Find "AB" and remove it. s becomes "FC".
    1. No more "AB" or "CD" can be found. The final length is 2.
class Solution {    public int minLength(String s) {        StringBuilder sb = new StringBuilder(s);        boolean found = true;        while (found) {            found = false;            int abIndex = sb.indexOf("AB");            if (abIndex != -1) {                sb.delete(abIndex, abIndex + 2);                found = true;                // Restart search from the beginning as new pairs might have formed                continue;             }                        int cdIndex = sb.indexOf("CD");            if (cdIndex != -1) {                sb.delete(cdIndex, cdIndex + 2);                found = true;            }        }        return sb.length();    }}

Complexity

Time

O(N^2), where N is the length of the string. The outer loop can run up to N/2 times, as we remove 2 characters in each successful iteration. Inside the loop, `indexOf` and `delete` on a `StringBuilder` can take up to O(N) time. Thus, the total time complexity is O(N * N) = O(N^2).

Space

O(N), where N is the length of the string. This is required to store the `StringBuilder`.

Trade-offs

Pros

  • Conceptually simple and easy to implement.

  • Directly follows the logic of the problem description.

Cons

  • Inefficient due to repeated scanning of the string.

  • String/StringBuilder manipulation operations (indexOf, delete) inside a loop lead to quadratic time complexity, which can be slow for larger inputs.

Solutions

class Solution { public int minLength ( String s ) { Deque < Character > stk = new ArrayDeque <>(); stk . push ( ' ' ); for ( char c : s . toCharArray ()) { if (( c == 'B' && stk . peek () == 'A' ) || ( c == 'D' && stk . peek () == 'C' )) { stk . pop (); } else { stk . push ( c ); } } return stk . size () - 1 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem