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

Dada una string S que consta de los caracteres ‘(‘, ‘)’, ‘[‘, ‘]’, ‘{‘, ‘}’ , la tarea es eliminar todas las subsecuencias de paréntesis equilibradas de la string e imprimir los caracteres restantes.

Ejemplos:

Entrada: S =“((){()({})”
Salida: “({“
Explicación:

1. S[1] y S[2] forman una secuencia regular de paréntesis. Por lo tanto, quítelos de la string. S = “({()({})”
2. S[2] y S[3] son ​​una secuencia de paréntesis regular. Por lo tanto, quítelos de la string. S = “({({})”
3. La string S[2…4] es una secuencia de paréntesis regular. Por lo tanto, quítelos de la string. S = “({“

La string restante no contiene ninguna secuencia de paréntesis regular. Por lo tanto, imprima todos los caracteres restantes.

Entrada: S = “{[}])(“
Salida: “)(” 

Enfoque: La idea es utilizar la estructura de datos Stack para resolver este problema. Siga los pasos a continuación para resolver el problema:

• Inicialice tres pilas , digamos A , B y C , para almacenar cada tipo de paréntesis.
• Inicialice una array booleana, digamos vis[] , para marcar los caracteres ya visitados.
• Almacene índices de char ‘(‘ en la pila A. De manera similar, las pilas B y C almacenan las posiciones de ‘{‘ y ‘[‘ en la string.
• Recorra los caracteres de la string str y realice lo siguiente:
  • Si el carácter actual es ‘ ) ‘:
    • Si la pila A no está vacía , marque el carácter actual en la string y vis[A.top()] como falso .
    • Pop el elemento superior de la pila A .
  • Si el carácter actual es ‘ }’:
    • Si la pila B no está vacía, marque el carácter actual en la string y vis[B.top()] como falso .
    • Extraiga el elemento superior de la pila B .
  • Si el carácter actual es ‘]’:
    • Si la pila C no está vacía, marque el carácter actual en la string y vis[C.top()] como falso.
    • Extraiga el elemento superior de la pila C .
• Después de completar todas las operaciones, imprima los caracteres de la string cuyo índice está marcado como verdadero en la array vis[] .

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

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to remove all possible valid
// bracket subsequences
void removeValidBracketSequences(string& str,
                                 int N)
{
 
    // Stores indexes of '(' in
    // valid subsequences
    stack<int> A;
 
    // Stores indexes of '{' in
    // valid subsequences
    stack<int> B;
 
    // Stores indexes of '[' in
    // valid subsequences
    stack<int> C;
 
    // vis[i]: Check if character at
    // i-th index is removed or not
    bool vis[N];
 
    // Mark vis[i] as not removed
    memset(vis, true, sizeof(vis));
 
    // Iterate over the characters of string
    for (int i = 0; i < N; i++) {
 
        // If current character is '('
        if (str[i] == '(') {
            A.push(i);
        }
 
        // If current character is '{'
        else if (str[i] == '{') {
            B.push(i);
        }
 
        // If current character is '['
        else if (str[i] == '[') {
            C.push(i);
        }
 
        // If current character is ')' and
        // top element of A is '('
        else if (str[i] == ')' && !A.empty()) {
 
            // Mark the top element
            // of A as removed
            vis[A.top()] = false;
            A.pop();
 
            // Mark current character
            // as removed
            vis[i] = false;
        }
 
        // If current character is '}' and
        // top element of B is '{'
        else if (str[i] == '}' && !B.empty()) {
 
            // Mark the top element
            // of B as removed
            vis[B.top()] = false;
            B.pop();
 
            // Mark current character
            // as removed
            vis[i] = false;
        }
 
        // If current character is ']' and
        // top element of B is '['
        else if (str[i] == ']' && !C.empty()) {
 
            // Mark the top element
            // of C as removed
            vis[C.top()] = false;
            C.pop();
 
            // Mark current character
            // as removed
            vis[i] = false;
        }
    }
 
    // Print the remaining characters
    // which is not removed from S
    for (int i = 0; i < N; ++i) {
 
        if (vis[i])
            cout << str[i];
    }
}
 
// Driver Code
int main()
{
    // Given string
    string str = "((){()({})";
 
    // Size of the string
    int N = str.length();
 
    // Function Call
    removeValidBracketSequences(str, N);
 
    return 0;
}

// Java program of the above approach
import java.util.*;
public class GFG
{
 
  // Function to remove all possible valid
  // bracket subsequences
  static void removeValidBracketSequences(String str, int N)
  {
 
    // Stores indexes of '(' in
    // valid subsequences
    Vector<Integer> A = new Vector<Integer>(); 
 
    // Stores indexes of '{' in
    // valid subsequences
    Vector<Integer> B = new Vector<Integer>();
 
    // Stores indexes of '[' in
    // valid subsequences
    Vector<Integer> C = new Vector<Integer>();
 
    // vis[i]: Check if character at
    // i-th index is removed or not
    boolean[] vis = new boolean[N];
 
    // Mark vis[i] as not removed
    for(int i = 0; i < N; i++)
    {
      vis[i] = true;
    }
 
    // Iterate over the characters of string
    for (int i = 0; i < N; i++) {
 
      // If current character is '('
      if (str.charAt(i) == '(') {
        A.add(i);
      }
 
      // If current character is '{'
      else if (str.charAt(i) == '{') {
        B.add(i);
      }
 
      // If current character is '['
      else if (str.charAt(i) == '[') {
        C.add(i);
      }
 
      // If current character is ')' and
      // top element of A is '('
      else if (str.charAt(i) == ')' && (A.size() > 0)) {
 
        // Mark the top element
        // of A as removed
        vis[A.get(A.size() - 1)] = false;
        A.remove(A.size() - 1);
 
        // Mark current character
        // as removed
        vis[i] = false;
      }
 
      // If current character is '}' and
      // top element of B is '{'
      else if (str.charAt(i) == '}' && (B.size() > 0)) {
 
        // Mark the top element
        // of B as removed
        vis[B.get(B.size() - 1)] = false;
        B.remove(B.size() - 1);
 
        // Mark current character
        // as removed
        vis[i] = false;
      }
 
      // If current character is ']' and
      // top element of B is '['
      else if (str.charAt(i) == ']' && (C.size() > 0)) {
 
        // Mark the top element
        // of C as removed
        vis[C.get(C.size() - 1)] = false;
        C.remove(C.size() - 1);
 
        // Mark current character
        // as removed
        vis[i] = false;
      }
    }
 
    // Print the remaining characters
    // which is not removed from S
    for (int i = 0; i < N; ++i)
    {
      if (vis[i])
        System.out.print(str.charAt(i));
    }
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    // Given string
    String str = "((){()({})";
 
    // Size of the string
    int N = str.length();
 
    // Function Call
    removeValidBracketSequences(str, N);
  }
}
 
// This code is contributed by divyeshrabadiya07.

# Python3 program of the above approach
 
# Function to remove all possible valid
# bracket subsequences
def removeValidBracketSequences(str, N):
     
    # Stores indexes of '(' in
    # valid subsequences
    A = []
 
    # Stores indexes of '{' in
    # valid subsequences
    B = []
 
    # Stores indexes of '[' in
    # valid subsequences
    C = []
 
    # vis[i]: Check if character at
    # i-th index is removed or not
    vis = [True for i in range(N)]
 
    # Iterate over the characters of string
    for i in range(N):
 
        # If current character is '('
        if (str[i] == '('):
            A.append(i)
         
        # If current character is '{'
        elif (str[i] == '{'):
            B.append(i)
 
        # If current character is '['
        elif (str[i] == '['):
            C.append(i)
 
        # If current character is ')' and
        # top element of A is '('
        elif(str[i] == ')' and len(A) != 0):
             
            # Mark the top element
            # of A as removed
            vis[A[-1]] = False
            A.pop()
 
            # Mark current character
            # as removed
            vis[i] = False
 
        # If current character is '}' and
        # top element of B is '{'
        elif (str[i] == '}' and len(B) != 0):
 
            # Mark the top element
            # of B as removed
            vis[B[-1]] = False
            B.pop()
 
            # Mark current character
            # as removed
            vis[i] = False
 
        # If current character is ']' and
        # top element of B is '['
        elif(str[i] == ']' and len(C) != 0):
 
            # Mark the top element
            # of C as removed
            vis[C[-1]] = False
            C.pop()
 
            # Mark current character
            # as removed
            vis[i] = False
 
    # Print the remaining characters
    # which is not removed from S
    for i in range(N):
        if (vis[i]):
            print(str[i], end = '')
     
# Driver Code
if __name__=='__main__':
 
    # Given string
    str = "((){()({})"
 
    # Size of the string
    N = len(str)
 
    # Function Call
    removeValidBracketSequences(str, N)
 
# This code is contributed by rutvik_56

// C# program of the above approach
using System;
using System.Collections.Generic;
class GFG {
     
    // Function to remove all possible valid
    // bracket subsequences
    static void removeValidBracketSequences(string str, int N)
    {
       
        // Stores indexes of '(' in
        // valid subsequences
        List<int> A = new List<int>();
       
        // Stores indexes of '{' in
        // valid subsequences
        List<int> B = new List<int>();
       
        // Stores indexes of '[' in
        // valid subsequences
        List<int> C = new List<int>();
       
        // vis[i]: Check if character at
        // i-th index is removed or not
        bool[] vis = new bool[N];
         
        // Mark vis[i] as not removed
        for(int i = 0; i < N; i++)
        {
            vis[i] = true;
        }
       
        // Iterate over the characters of string
        for (int i = 0; i < N; i++) {
       
            // If current character is '('
            if (str[i] == '(') {
                A.Add(i);
            }
       
            // If current character is '{'
            else if (str[i] == '{') {
                B.Add(i);
            }
       
            // If current character is '['
            else if (str[i] == '[') {
                C.Add(i);
            }
       
            // If current character is ')' and
            // top element of A is '('
            else if (str[i] == ')' && (A.Count > 0)) {
       
                // Mark the top element
                // of A as removed
                vis[A[A.Count - 1]] = false;
                A.RemoveAt(A.Count - 1);
       
                // Mark current character
                // as removed
                vis[i] = false;
            }
       
            // If current character is '}' and
            // top element of B is '{'
            else if (str[i] == '}' && (B.Count > 0)) {
       
                // Mark the top element
                // of B as removed
                vis[B[B.Count - 1]] = false;
                B.RemoveAt(B.Count - 1);
       
                // Mark current character
                // as removed
                vis[i] = false;
            }
       
            // If current character is ']' and
            // top element of B is '['
            else if (str[i] == ']' && (C.Count > 0)) {
       
                // Mark the top element
                // of C as removed
                vis[C[C.Count - 1]] = false;
                C.RemoveAt(C.Count - 1);
       
                // Mark current character
                // as removed
                vis[i] = false;
            }
        }
       
        // Print the remaining characters
        // which is not removed from S
        for (int i = 0; i < N; ++i) {
       
            if (vis[i])
                Console.Write(str[i]);
        }
    }
 
  // Driver code
  static void Main()
  {
     
    // Given string
    string str = "((){()({})";
   
    // Size of the string
    int N = str.Length;
   
    // Function Call
    removeValidBracketSequences(str, N);
  }
}
 
// This code is contributed by divyesh072019.

<script>
    // Javascript program of the above approach
     
    // Function to remove all possible valid
    // bracket subsequences
    function removeValidBracketSequences(str, N)
    {
        
        // Stores indexes of '(' in
        // valid subsequences
        let A = [];
        
        // Stores indexes of '{' in
        // valid subsequences
        let B = [];
        
        // Stores indexes of '[' in
        // valid subsequences
        let C = [];
        
        // vis[i]: Check if character at
        // i-th index is removed or not
        let vis = new Array(N);
          
        // Mark vis[i] as not removed
        for(let i = 0; i < N; i++)
        {
            vis[i] = true;
        }
        
        // Iterate over the characters of string
        for (let i = 0; i < N; i++) {
        
            // If current character is '('
            if (str[i] == '(') {
                A.push(i);
            }
        
            // If current character is '{'
            else if (str[i] == '{') {
                B.push(i);
            }
        
            // If current character is '['
            else if (str[i] == '[') {
                C.push(i);
            }
        
            // If current character is ')' and
            // top element of A is '('
            else if (str[i] == ')' && (A.length > 0)) {
        
                // Mark the top element
                // of A as removed
                vis[A[A.length - 1]] = false;
                A.pop();
        
                // Mark current character
                // as removed
                vis[i] = false;
            }
        
            // If current character is '}' and
            // top element of B is '{'
            else if (str[i] == '}' && (B.length > 0)) {
        
                // Mark the top element
                // of B as removed
                vis[B[B.length - 1]] = false;
                B.pop();
        
                // Mark current character
                // as removed
                vis[i] = false;
            }
        
            // If current character is ']' and
            // top element of B is '['
            else if (str[i] == ']' && (C.length > 0)) {
        
                // Mark the top element
                // of C as removed
                vis[C[C.length - 1]] = false;
                C.pop();
        
                // Mark current character
                // as removed
                vis[i] = false;
            }
        }
        
        // Print the remaining characters
        // which is not removed from S
        for (let i = 0; i < N; ++i) {
        
            if (vis[i])
                document.write(str[i]);
        }
    }
     
    // Given string
    let str = "((){()({})";
    
    // Size of the string
    let N = str.length;
    
    // Function Call
    removeValidBracketSequences(str, N);
   
  // This code is contributed by suresh07
</script>

({

Complejidad temporal: O(N)
Espacio auxiliar: O(N)