Reducir la string a la longitud mínima con la operación dada

Dada una string str que consta de caracteres en minúsculas y mayúsculas, la tarea es encontrar la longitud mínima posible a la que se puede reducir la string después de realizar la operación dada cualquier número de veces. En una sola operación, se pueden eliminar dos caracteres consecutivos si representan el mismo carácter en casos diferentes, es decir, se pueden eliminar «aA» y «Cc» , pero no se pueden eliminar «cc» y «EE» .
Ejemplos: 
 

Entrada: str = “ASbBsd” 
Salida: 2 
Operaciones 1: “AS bB sd” -> “ASsd” 
Operaciones 2: “A Ss d” -> “Ad” 
La string no se puede reducir más.
Entrada: str = “AsSaDda” 
Salida: 1 
Operaciones 1: “A sS aDda” -> “AaDda” 
Operaciones 2: “ Aa Dda” -> “Dda” 
Operaciones 3: “ Dd a” -> “a” 
 

Acercarse: 
 

• Cree una pila para almacenar los caracteres de la string.
• Para cada carácter de la string a partir del primer carácter, si la pila está vacía, inserte el carácter actual en la pila.
• De lo contrario, haga coincidir el carácter actual con la parte superior de la pila, si solo difieren en el caso, extraiga el elemento de la pila y continúe.
• Si no son iguales, empuje el elemento actual a la pila y repita los pasos anteriores para el resto de la string.
• El tamaño de la pila al final es la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum
// possible length str can be reduced
// to with the given operation
int minLength(string str, int len)
{
 
    // Stack to store the characters
    // of the given string
    stack<char> s;
 
    // For every character of the string
    for (int i = 0; i < len; i++) {
 
        // If the stack is empty then push the
        // current character in the stack
        if (s.empty()) {
            s.push(str[i]);
        }
        else {
 
            // Get the top character
            char c = s.top();
 
            // If the top element is not equal
            // to the current element and it
            // only differs in the case
            if (c != str[i]
                && toupper(c) == toupper(str[i])) {
 
                // Pop the top element from stack
                s.pop();
            }
 
            // Else push the current element
            else {
                s.push(str[i]);
            }
        }
    }
 
    return s.size();
}
 
// Driver code
int main()
{
    string str = "ASbBsd";
    int len = str.length();
 
    cout << minLength(str, len);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the minimum
// possible length str can be reduced
// to with the given operation
static int minLength(String str, int len)
{
 
    // Stack to store the characters
    // of the given string
    Stack<Character> s = new Stack<Character>();
 
    // For every character of the string
    for (int i = 0; i < len; i++)
    {
 
        // If the stack is empty then push the
        // current character in the stack
        if (s.empty())
        {
            s.push(str.charAt(i));
        }
        else
        {
 
            // Get the top character
            char c = s.peek();
 
            // If the top element is not equal
            // to the current element and it
            // only differs in the case
            if (c != str.charAt(i) &&
                Character.toUpperCase(c) ==
                Character.toUpperCase((str.charAt(i))))
            {
 
                // Pop the top element from stack
                s.pop();
            }
 
            // Else push the current element
            else
            {
                s.push(str.charAt(i));
            }
        }
    }
    return s.size();
}
 
// Driver code
public static void main(String []args)
{
    String str = "ASbBsd";
    int len = str.length();
 
    System.out.println(minLength(str, len));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 implementation of the approach
 
# Function to return the minimum
# possible length str can be reduced
# to with the given operation
def minLength(string, l) :
 
    # Stack to store the characters
    # of the given string
    s = [];
 
    # For every character of the string
    for i in range(l) :
 
        # If the stack is empty then push the
        # current character in the stack
        if (len(s) == 0) :
            s.append(string[i]);
             
        else :
 
            # Get the top character
            c = s[-1];
             
            # If the top element is not equal
            # to the current element and it
            # only differs in the case
            if (c != string[i] and
                c.upper() == string[i].upper()) :
 
                # Pop the top element from stack
                s.pop();
 
            # Else push the current element
            else :
                s.append(string[i]);
 
    return len(s);
 
# Driver code
if __name__ == "__main__" :
 
    string = "ASbBsd";
    l = len(string);
 
    print(minLength(string, l));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to return the minimum
// possible length str can be reduced
// to with the given operation
static int minLength(String str, int len)
{
 
    // Stack to store the characters
    // of the given string
    Stack<char> s = new Stack<char>();
 
    // For every character of the string
    for (int i = 0; i < len; i++)
    {
 
        // If the stack is empty then push the
        // current character in the stack
        if (s.Count==0)
        {
            s.Push(str[i]);
        }
        else
        {
 
            // Get the top character
            char c = s.Peek();
 
            // If the top element is not equal
            // to the current element and it
            // only differs in the case
            if (c != str[i] &&
                char.ToUpper(c) ==
                char.ToUpper((str[i])))
            {
 
                // Pop the top element from stack
                s.Pop();
            }
 
            // Else push the current element
            else
            {
                s.Push(str[i]);
            }
        }
    }
    return s.Count;
}
 
// Driver code
public static void Main(String []args)
{
    String str = "ASbBsd";
    int len = str.Length;
 
    Console.WriteLine(minLength(str, len));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
    // Javascript implementation of the approach
     
    // Function to return the minimum
    // possible length str can be reduced
    // to with the given operation
    function minLength(str, len)
    {
 
        // Stack to store the characters
        // of the given string
        let s = [];
 
        // For every character of the string
        for (let i = 0; i < len; i++)
        {
 
            // If the stack is empty then push the
            // current character in the stack
            if (s.length==0)
            {
                s.push(str[i]);
            }
            else
            {
 
                // Get the top character
                let c = s[s.length - 1];
 
                // If the top element is not equal
                // to the current element and it
                // only differs in the case
                if (c != str[i] &&
                    c.toUpperCase() ==
                    str[i].toUpperCase())
                {
 
                    // Pop the top element from stack
                    s.pop();
                }
 
                // Else push the current element
                else
                {
                    s.push(str[i]);
                }
            }
        }
        return s.length;
    }
     
    let str = "ASbBsd";
    let len = str.length;
   
    document.write(minLength(str, len));
 
</script>

2

Complejidad temporal : O(N).
Espacio Auxiliar : O(N).