2696. Minimum String Length After Removing Substrings

[mah-shamim]

Topics: String, Stack, Simulation

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.

Hint:

1. Can we use brute force to solve the problem?
2. Repeatedly traverse the string to find and remove the substrings “AB” and “CD” until no more occurrences exist.

[kovatz]

We'll use a stack to handle the removal of substrings "AB" and "CD". The stack approach ensures that we efficiently remove these substrings as they occur during traversal of the string.

Approach:

1. Use a Stack:
   • Traverse the string character by character.
   • Push each character onto the stack.
   • If the top two characters on the stack form the substring "AB" or "CD", pop these two characters from the stack (remove them).
   • Continue this process for all characters in the input string.
2. Final String:
   • At the end of the traversal, the stack will contain the reduced string.
   • The minimum possible length will be the size of the stack.

Let's implement this solution in PHP: 2696. Minimum String Length After Removing Substrings

<?php
/**
 * @param String $s
 * @return Integer
 */
function minLengthAfterRemovals($s) {
    // Initialize an empty stack
    $stack = [];
    
    // Traverse through each character in the input string
    for ($i = 0; $i < strlen($s); $i++) {
        $currentChar = $s[$i];
        
        // Check if the top of the stack forms "AB" or "CD" with the current character
        if (!empty($stack)) {
            $topChar = end($stack);
            
            // Remove "AB" or "CD" if found
            if (($topChar == 'A' && $currentChar == 'B') || ($topChar == 'C' && $currentChar == 'D')) {
                array_pop($stack); // Remove the top element from the stack
                continue; // Skip adding the current character
            }
        }
        
        // If no removals, add the current character to the stack
        $stack[] = $currentChar;
    }
    
    // The minimum possible length is the size of the stack
    return count($stack);
}

// Example usage:
echo minLengthAfterRemovals("ABFCACDB"); // Output: 2
echo "\n";
echo minLengthAfterRemovals("ACBBD");    // Output: 5
?>

Explanation:

• We initialize an empty stack ($stack).
• Loop through each character of the string s.
• Check the top character of the stack:
  • If the top character and the current character form the substrings "AB" or "CD", we remove the top character using array_pop.
  • Otherwise, push the current character onto the stack.
• The stack will hold the characters that remain after all possible removals.
• Finally, count($stack) gives the length of the resulting string.

Complexity:

• Time Complexity: O(n), where n is the length of the string. Each character is processed at most twice (once pushed, once popped).
• Space Complexity: O(n) for the stack, in the worst case where no removals are possible.

This solution effectively minimizes the string by removing all possible occurrences of "AB" and "CD" until no more can be found.

[mah-shamim]

Thanks to solve the "Minimum String Length After Removing Substrings" problem

[kovatz]

Thanks