Encuentre una secuencia de paréntesis válida de longitud K a partir de una secuencia de paréntesis válida dada

Posted on by Rudeus Greyrat

Dada una string S de secuencia de paréntesis válida de longitud N y un número entero par K , la tarea es encontrar la secuencia de paréntesis válida de longitud K que también es una subsecuencia de la string dada.

Nota: Puede haber más de una secuencia válida, imprima cualquiera de ellas.

Ejemplos:

Entrada: S = “()()()”, K = 4
Salida:()()
Explicación:
La string “()()” es una subsecuencia de longitud 4 que es una secuencia de paréntesis válida.

Entrada: S = “()(())”, K = 6
Salida:()(())
Explicación:
La string “()(())” es una subsecuencia de longitud 6 que es una secuencia de paréntesis válida.

Enfoque ingenuo: la idea es generar todas las subsecuencias posibles de longitud K de la string dada e imprimir cualquiera de las strings que tenga una secuencia de paréntesis válida.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(K)

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando un Stack . La idea es atravesar la string dada y cuando se encuentra un carácter de paréntesis abierto, empujarlo a la pila, extraer un carácter de él. En consecuencia, incremente el contador cada vez que aparezca un carácter. Siga los pasos a continuación para resolver el problema: 

  1. Cree una pila y la array booleana, inicializada en false .
  2. Recorra la string dada y, si se encuentra un paréntesis de apertura, inserte ese índice en la pila.
  3. De lo contrario, si se encuentra una llave de cierre: 
    • Extrae el elemento superior de la pila
    • Incrementa el contador en 2
    • Marque los índices emergentes y actuales como verdaderos.
  4. Si el contador excede K , termine.
  5. Después de atravesar, agregue todos los caracteres juntos, de izquierda a derecha, lo que se marca como verdadero. Imprime la string resultante formada.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
// Function to find the subsequence
// of length K forming valid sequence
string findString(string s, int k)
{
    int n = s.length();
 
    // Stores the resultant string
    string ans = "";
    stack<int> st;
 
    // Check whether character at
    // index i is visited or not
    vector<bool> vis(n, false);
    int count = 0;
 
    // Traverse the string
    for (int i = 0; i < n; ++i) {
 
        // Push index of open bracket
        if (s[i] == '(') {
            st.push(i);
        }
 
        // Pop and mark visited
        if (count < k && s[i] == ')') {
 
            vis[st.top()] = 1;
            st.pop();
            vis[i] = true;
 
            // Increment count by 2
            count += 2;
        }
    }
 
    // Append the characters and create
    // the resultant string
    for (int i = 0; i < n; ++i) {
 
        if (vis[i] == true) {
            ans += s[i];
        }
    }
 
    // Return the resultant string
    return ans;
}
 
// Driver Code
int main()
{
    string s = "()()()";
    int K = 2;
 
    // Function Call
    cout << findString(s, K);
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the subsequence
// of length K forming valid sequence
static String findString(String s, int k)
{
    int n = s.length();
 
    // Stores the resultant String
    String ans = " ";
    Stack<Integer> st = new Stack<>();
 
    // Check whether character at
    // index i is visited or not
    boolean []vis = new boolean[n];
     
    // Vector<boolean> vis(n, false);
    int count = 0;
 
    // Traverse the String
    for(int i = 0; i < n; ++i)
    {
         
        // Push index of open bracket
        if (s.charAt(i) == '(')
        {
            st.add(i);
        }
 
        // Pop and mark visited
        if (count < k && s.charAt(i) == ')')
        {
            vis[st.peek()] = true;
            st.pop();
            vis[i] = true;
 
            // Increment count by 2
            count += 2;
        }
    }
 
    // Append the characters and create
    // the resultant String
    for(int i = 0; i < n; ++i)
    {
        if (vis[i] == true)
        {
            ans += s.charAt(i);
        }
    }
 
    // Return the resultant String
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    String s = "()()()";
    int K = 2;
 
    // Function call
    System.out.print(findString(s, K));
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python3 program for the above approach
 
# Function to find the subsequence
# of length K forming valid sequence
def findString(s, k):
     
    n = len(s)
 
    # Stores the resultant string
    ans = ""
    st = []
 
    # Check whether character at
    # index i is visited or not
    vis = [False] * n
    count = 0
 
    # Traverse the string
    for i in range(n):
 
        # Push index of open bracket
        if (s[i] == '('):
            st.append(i)
 
        # Pop and mark visited
        if (count < k and s[i] == ')'):
            vis[st[-1]] = 1
            del st[-1]
            vis[i] = True
 
            # Increment count by 2
            count += 2
 
    # Append the characters and create
    # the resultant string
    for i in range(n):
        if (vis[i] == True):
            ans += s[i]
             
    # Return the resultant string
    return ans
 
# Driver Code
if __name__ == '__main__':
     
    s = "()()()"
    K = 2
 
    # Function call
    print(findString(s, K))
 
# This code is contributed by mohit kumar 29

C#

// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to find the
// subsequence of length
// K forming valid sequence
static String findString(String s,
                         int k)
{
  int n = s.Length;
 
  // Stores the resultant String
  String ans = " ";
  Stack<int> st = new Stack<int>();
 
  // Check whether character at
  // index i is visited or not
  bool []vis = new bool[n];
 
  // List<bool> vis(n, false);
  int count = 0;
 
  // Traverse the String
  for(int i = 0; i < n; ++i)
  {
    // Push index of open bracket
    if (s[i] == '(')
    {
      st.Push(i);
    }
 
    // Pop and mark visited
    if (count < k && s[i] == ')')
    {
      vis[st.Peek()] = true;
      st.Pop();
      vis[i] = true;
 
      // Increment count by 2
      count += 2;
    }
  }
 
  // Append the characters and create
  // the resultant String
  for(int i = 0; i < n; ++i)
  {
    if (vis[i] == true)
    {
      ans += s[i];
    }
  }
 
  // Return the resultant String
  return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
  String s = "()()()";
  int K = 2;
 
  // Function call
  Console.Write(findString(s, K));
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
      // JavaScript program for
      // the above approach
       
      // Function to find the
      // subsequence of length
      // K forming valid sequence
      function findString(s, k) {
        var n = s.length;
 
        // Stores the resultant String
        var ans = " ";
        var st = [];
 
        // Check whether character at
        // index i is visited or not
        var vis = new Array(n);
 
        // List<bool> vis(n, false);
        var count = 0;
 
        // Traverse the String
        for (var i = 0; i < n; ++i) {
          // Push index of open bracket
          if (s[i] === "(") {
            st.push(i);
          }
 
          // Pop and mark visited
          if (count < k && s[i] === ")") {
            vis[st[st.length - 1]] = true;
            st.pop();
            vis[i] = true;
 
            // Increment count by 2
            count += 2;
          }
        }
 
        // Append the characters and create
        // the resultant String
        for (var i = 0; i < n; ++i) {
          if (vis[i] === true) {
            ans += s[i];
          }
        }
 
        // Return the resultant String
        return ans;
      }
 
      // Driver Code
      var s = "()()()";
      var K = 2;
 
      // Function call
      document.write(findString(s, K));
       
</script>
Producción: 

()

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.

Publicación traducida automáticamente

Artículo escrito por dreamer07 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *