Minimice la longitud eliminando las subsecuencias que forman paréntesis válidos de una string dada

Dada una string S que consta de ‘(‘, ‘)’, ‘[‘ y ‘]’ , la tarea es encontrar el recuento mínimo de caracteres restantes en la string eliminando las subsecuencias del paréntesis válido.

Ejemplos:

Entrada: S = “[]])([” 
Salida: 4 
Explicación: 
Eliminar la subsecuencia { str[0], str[1] } modifica S a “])([“. 
Por lo tanto, la salida requerida es 4.

Entrada: S = “([)(])” 
Salida: 0 
Explicación: 
Eliminar la subsecuencia { str[0], str[2] } modifica S a “[(])”. 
Eliminar la subsecuencia { str[0], str[2] } modifica S a “()”. 
Eliminar la subsecuencia { str[0], str[1] } modifica S a “”. 
Por lo tanto, la salida requerida es 0.

Enfoque: El problema se puede resolver usando Stack . Siga los pasos a continuación para resolver el problema:

• La idea es manejar el paréntesis redondo, ‘()’ y el paréntesis de corchete, ‘[]’ en dos pilas separadas.
• Inicialice dos variables, por ejemplo, roundCount y squareCount para almacenar el recuento de paréntesis de apertura en paréntesis válidos de ‘()’ y ‘[]’ respectivamente.
• Itere sobre cada carácter de la string dada y calcule la longitud del paréntesis válido de ‘()’ y ‘[]’ usando dos pilas diferentes.
• Finalmente, imprima el valor de (N – 2 * (recuento redondo + recuento cuadrado)) .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum count of remaining
// characters left into the string by removing
// the valid subsequences
void deleteSubseq(string s)
{
 
    // Length of the string
    int N = s.size();
 
    // Stores opening parenthesis
    // '(' of the given string
    stack<char> roundStk;
 
    // Stores square parenthesis
    // '[' of the given string
    stack<char> squareStk;
 
    // Stores count of opening parenthesis '('
    // in valid subsequences
    int roundCount = 0;
 
    // Stores count of opening parenthesis '['
    // in valid subsequences
    int squareCount = 0;
 
    // Iterate over each
    // characters of S
    for (int i = 0; i < N; i++)
    {
 
        // If current character is '['
        if (s[i] == '[')
        {
 
            // insert into stack
            squareStk.push(s[i]);
        }
 
        // If i is equal to ']'
        else if (s[i] == ']')
        {
 
            // If stack is not empty and
            // top element of stack is '['
            if (squareStk.size() != 0
                && squareStk.top() == '[')
            {
 
                // Remove top element from stack
                squareStk.pop();
 
                // Update squareCount
                squareCount += 1;
            }
        }
 
        // If current character is '('
        else if (s[i] == '(')
        {
 
            // Insert into stack
            roundStk.push(s[i]);
        }
 
        // If i is equal to ')'
        else
        {
 
            // If stack is not empty and
            // top element of stack is '('
            if (roundStk.size() != 0
                && squareStk.top() == '(')
            {
 
                // Remove top element from stack
                squareStk.pop();
 
                // Update roundCount
                roundCount += 1;
            }
        }
    }
 
    // Print the minimum number of remaining
    // characters left into S
    cout << (N - (2 * squareCount + 2 * roundCount));
}
 
// Driver code
int main()
{
 
    // input string
    string s = "[]])([";
 
    // function call
    deleteSubseq(s);
}
 
// This code is contributed by gauravrajput1

/*package whatever //do not write package name here */
 
// Java program for the above approach
import java.io.*;
import java.util.Stack;
class GFG
{
 
  // Function to find the minimum count of remaining
  // characters left into the string by removing
  // the valid subsequences
  public static void deleteSubseq(String s)
  {
 
    // Length of the string
    int N = s.length();
 
    // Stores opening parenthesis
    // '(' of the given string
    Stack<Character> roundStk = new Stack<>();
 
    // Stores square parenthesis
    // '[' of the given string
    Stack<Character> squareStk = new Stack<>();
 
    // Stores count of opening parenthesis '('
    // in valid subsequences
    int roundCount = 0;
 
    // Stores count of opening parenthesis '['
    // in valid subsequences
    int squareCount = 0;
 
    // Iterate over each
    // characters of S
    for (int i = 0; i < N; i++)
    {
 
      // If current character is '['
      if (s.charAt(i) == '[')
      {
 
        // insert into stack
        squareStk.push(s.charAt(i));
      }
 
      // If i is equal to ']'
      else if (s.charAt(i) == ']')
      {
 
        // If stack is not empty and
        // top element of stack is '['
        if (squareStk.size() != 0
            && squareStk.peek() == '[')
        {
 
          // Remove top element from stack
          squareStk.pop();
 
          // Update squareCount
          squareCount += 1;
        }
      }
 
      // If current character is '('
      else if (s.charAt(i) == '(')
      {
 
        // Insert into stack
        roundStk.push(s.charAt(i));
      }
 
      // If i is equal to ')'
      else
      {
 
        // If stack is not empty and
        // top element of stack is '('
        if (roundStk.size() != 0
            && squareStk.peek() == '(')
        {
 
          // Remove top element from stack
          squareStk.pop();
 
          // Update roundCount
          roundCount += 1;
        }
      }
    }
 
    // Print the minimum number of remaining
    // characters left into S
    System.out.println(
      N - (2 * squareCount + 2 * roundCount));
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    // input string
    String s = "[]])([";
 
    // function call
    deleteSubseq(s);
  }
}
 
// This code is contributed by aditya7409

# Python program for the above approach
 
# Function to find the minimum count of remaining
# characters left into the string by removing
# the valid subsequences
def deleteSubseq(S):
 
    # Length of the string
    N = len(S)
 
    # Stores opening parenthesis
    # '(' of the given string
    roundStk = []
 
    # Stores square parenthesis
    # '[' of the given string
    squareStk = []
 
    # Stores count of opening parenthesis '('
    # in valid subsequences
    roundCount = 0
 
    # Stores count of opening parenthesis '['
    # in valid subsequences
    squareCount = 0
 
    # Iterate over each
    # characters of S
    for i in S:
 
        # If current character is '['
        if i == '[':
 
            # Insert into stack
            squareStk.append(i)
 
        # If i is equal to ']'
        elif i == ']':
             
             
            # If stack is not empty and
            # top element of stack is '['
            if squareStk and squareStk[-1] == '[':
                 
                 
                # Remove top element from stack
                squareStk.pop()
                 
                 
                # Update squareCount
                squareCount += 1
 
        # If current character is '('
        elif i == '(':
             
             
            # Insert into stack
            roundStk.append(i)
        else:
             
             
            # If stack is not empty and
            # top element of stack is '('
            if roundStk and roundStk[-1] == '(':
                 
                 
                # Remove top element from stack
                roundStk.pop()
                 
                 
                # Update roundCount
                roundCount += 1
 
 
    # Print the minimum number of remaining
    # characters left into S
    print(N - (2 * squareCount + 2 * roundCount))
 
 
# Driver Code
if __name__ == '__main__':
     
    # Given string
    S = '[]])(['
 
    # Function Call
    deleteSubseq(S)

/*package whatever //do not write package name here */
 
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
 
  // Function to find the minimum count of remaining
  // characters left into the string by removing
  // the valid subsequences
  public static void deleteSubseq(String s)
  {
 
    // Length of the string
    int N = s.Length;
 
    // Stores opening parenthesis
    // '(' of the given string
    Stack<char> roundStk = new Stack<char>();
 
    // Stores square parenthesis
    // '[' of the given string
    Stack<char> squareStk = new Stack<char>();
 
    // Stores count of opening parenthesis '('
    // in valid subsequences
    int roundCount = 0;
 
    // Stores count of opening parenthesis '['
    // in valid subsequences
    int squareCount = 0;
 
    // Iterate over each
    // characters of S
    for (int i = 0; i < N; i++)
    {
 
      // If current character is '['
      if (s[i] == '[')
      {
 
        // insert into stack
        squareStk.Push(s[i]);
      }
 
      // If i is equal to ']'
      else if (s[i] == ']')
      {
 
        // If stack is not empty and
        // top element of stack is '['
        if (squareStk.Count != 0
            && squareStk.Peek() == '[')
        {
 
          // Remove top element from stack
          squareStk.Pop();
 
          // Update squareCount
          squareCount += 1;
        }
      }
 
      // If current character is '('
      else if (s[i] == '(')
      {
 
        // Insert into stack
        roundStk.Push(s[i]);
      }
 
      // If i is equal to ')'
      else
      {
 
        // If stack is not empty and
        // top element of stack is '('
        if (roundStk.Count != 0
            && squareStk.Peek() == '(')
        {
 
          // Remove top element from stack
          squareStk.Pop();
 
          // Update roundCount
          roundCount += 1;
        }
      }
    }
 
    // Print the minimum number of remaining
    // characters left into S
    Console.WriteLine(
      N - (2 * squareCount + 2 * roundCount));
  }
 
  // Driver code
  public static void Main(String[] args)
  {
 
    // input string
    String s = "[]])([";
 
    // function call
    deleteSubseq(s);
  }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program for the above approach
 
// Function to find the minimum count of remaining
// characters left into the string by removing
// the valid subsequences
function deleteSubseq(s)
{
 
    // Length of the string
    var N = s.length;
 
    // Stores opening parenthesis
    // '(' of the given string
    var roundStk = [];
 
    // Stores square parenthesis
    // '[' of the given string
    var squareStk = [];
 
    // Stores count of opening parenthesis '('
    // in valid subsequences
    var roundCount = 0;
 
    // Stores count of opening parenthesis '['
    // in valid subsequences
    var squareCount = 0;
 
    // Iterate over each
    // characters of S
    for (var i = 0; i < N; i++)
    {
 
        // If current character is '['
        if (s[i] == '[')
        {
 
            // insert into stack
            squareStk.push(s[i]);
        }
 
        // If i is equal to ']'
        else if (s[i] == ']')
        {
 
            // If stack is not empty and
            // top element of stack is '['
            if (squareStk.length != 0
                && squareStk[squareStk.length-1] == '[')
            {
 
                // Remove top element from stack
                squareStk.pop();
 
                // Update squareCount
                squareCount += 1;
            }
        }
 
        // If current character is '('
        else if (s[i] == '(')
        {
 
            // Insert into stack
            roundStk.push(s[i]);
        }
 
        // If i is equal to ')'
        else
        {
 
            // If stack is not empty and
            // top element of stack is '('
            if (roundStk.length != 0
                && squareStk[squareStk.length-1] == '(')
            {
 
                // Remove top element from stack
                squareStk.pop();
 
                // Update roundCount
                roundCount += 1;
            }
        }
    }
 
    // Print the minimum number of remaining
    // characters left into S
    document.write(N - (2 * squareCount + 2 * roundCount));
}
 
// Driver code
 
// input string
var s = "[]])([";
 
// function call
deleteSubseq(s);
 
 
</script>

4

Complejidad de tiempo: O(N) donde n es el número de elementos en una string dada. Como estamos usando un bucle para atravesar N veces, nos costará O (N) tiempo.
Espacio auxiliar: O(N), ya que estamos usando espacio adicional para la pila.