Dada una string numérica S formada únicamente por los caracteres ‘1’, ‘2’ y ‘3’ , la tarea es reemplazar los caracteres con un corchete abierto ( ‘(‘ ) o un corchete cerrado ( ‘)’ ) de modo que el la string recién formada se convierte en una secuencia de paréntesis balanceada .
Nota: Todas las ocurrencias de un carácter deben ser reemplazadas por los mismos paréntesis.
Ejemplos:
Entrada: S = “1123”
Salida: Sí, (())
Explicación: Reemplazo de ocurrencias del carácter ‘1’ con ‘(‘, ‘2’ con ‘)’ y ‘3’ con ‘)’. Por lo tanto, la secuencia de paréntesis obtenida es “(())”, que está balanceada.Entrada: S = “1121”
Salida : No
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Para una secuencia de corchetes balanceada , es necesario que el primer y último carácter sean corchetes abiertos y cerrados respectivamente. Por lo tanto, el primero y el último carácter deben ser diferentes.
- Si el primero y el último carácter de una string son iguales, entonces es imposible obtener una secuencia de paréntesis balanceada.
- Si el primer y el último carácter de una string son diferentes, se reemplazan por corchetes abiertos y cerrados respectivamente. El tercer carácter se reemplaza por corchetes abiertos o cerrados .
- Verifique las dos formas de reemplazo uno por uno para el tercer carácter restante.
- Si ambos reemplazos del tercer carácter restante no pueden hacer una secuencia de paréntesis balanceada, entonces es imposible hacer una secuencia de paréntesis balanceada.
Siga los pasos a continuación para resolver el problema dado:
- Compruebe si el primer y el último carácter de la string S son iguales o no. Si se encuentra que es cierto, escriba “No” y regrese.
- Inicialice dos variables, digamos cntforOpen y cntforClose , para almacenar el recuento de paréntesis abiertos y cerrados.
- Iterar sobre los caracteres de la string y realizar las siguientes operaciones:
- Si el carácter actual es el mismo que el primer carácter de la string, incremente cntforOpen.
- Si el carácter actual es el mismo que el último carácter de la string, disminuya cntforOpen.
- Para el tercer carácter restante, incremente cntforOpen , es decir, reemplace ese carácter con ‘(‘ .
- Si en algún momento se encuentra que cntforOpen es negativo, entonces no se puede obtener una secuencia de paréntesis balanceada.
- De manera similar, verifique usando la variable cntforClose , es decir, reemplazando el tercer carácter con ‘)’ .
- Si ninguno de los dos métodos anteriores genera una secuencia de paréntesis equilibrada, imprima «No» . De lo contrario, escriba «Sí».
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to check if the given // string can be converted to a // balanced bracket sequence or not void balBracketSequence(string str) { int n = str.size(); // Check if the first and // last characters are equal if (str[0] == str[n - 1]) { cout << "No" << endl; } else { // Initialize two variables to store // the count of open and closed brackets int cntForOpen = 0, cntForClose = 0; int check = 1; for (int i = 0; i < n; i++) { // If the current character is // same as the first character if (str[i] == str[0]) cntForOpen++; // If the current character is // same as the last character else if (str[i] == str[n - 1]) cntForOpen--; else cntForOpen++; // If count of open brackets // becomes less than 0 if (cntForOpen < 0) { check = 0; break; } } if (check && cntForOpen == 0) { cout << "Yes, "; // Print the new string for (int i = 0; i < n; i++) { if (str[i] == str[n - 1]) cout << ')'; else cout << '('; } return; } else { for (int i = 0; i < n; i++) { // If the current character is // same as the first character if (str[i] == str[0]) cntForClose++; else cntForClose--; // If bracket sequence // is not balanced if (cntForClose < 0) { check = 0; break; } } // Check for unbalanced // bracket sequence if (check && cntForClose == 0) { cout << "Yes, "; // Print the sequence for (int i = 0; i < n; i++) { if (str[i] == str[0]) cout << '('; else cout << ')'; } return; } } cout << "No"; } } // Driver Code int main() { // Given Input string str = "123122"; // Function Call balBracketSequence(str); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to check if the given // string can be converted to a // balanced bracket sequence or not static void balBracketSequence(String str) { int n = str.length(); // Check if the first and // last characters are equal if (str.charAt(0) == str.charAt(n - 1)) { System.out.println("No"); } else { // Initialize two variables to store // the count of open and closed brackets int cntForOpen = 0, cntForClose = 0; int check = 1; for (int i = 0; i < n; i++) { // If the current character is // same as the first character if (str.charAt(i) == str.charAt(0)) cntForOpen++; // If the current character is // same as the last character else if (str.charAt(i) == str.charAt(n - 1)) cntForOpen -= 1; else cntForOpen += 1; // If count of open brackets // becomes less than 0 if (cntForOpen < 0) { check = 0; break; } } if (check != 0 && cntForOpen == 0) { System.out.print("Yes, "); // Print the new string for (int i = 0; i < n; i++) { if (str.charAt(i) == str.charAt(n - 1)) System.out.print(')'); else System.out.print('('); } return; } else { for (int i = 0; i < n; i++) { // If the current character is // same as the first character if (str.charAt(i) == str.charAt(0)) cntForClose++; else cntForClose--; // If bracket sequence // is not balanced if (cntForClose < 0) { check = 0; break; } } // Check for unbalanced // bracket sequence if (check != 0 && cntForClose == 0) { System.out.print("Yes, "); // Print the sequence for (int i = 0; i < n; i++) { if (str.charAt(i) == str.charAt(0)) System.out.print('('); else System.out.print(')'); } return; } } System.out.print("No"); } } // Driver Code public static void main(String args[]) { // Given Input String str = "123122"; // Function Call balBracketSequence(str); } } // This code is contributed by ipg2016107.
Python3
# Python program for the above approach; # Function to check if the given # string can be converted to a # balanced bracket sequence or not def balBracketSequence(str): n = len(str) # Check if the first and # last characters are equal if (str[0] == str[n - 1]): print("No", end="") else: # Initialize two variables to store # the count of open and closed brackets cntForOpen = 0 cntForClose = 0 check = 1 for i in range(n): # If the current character is # same as the first character if (str[i] == str[0]): cntForOpen += 1 # If the current character is # same as the last character elif str[i] == str[n - 1] : cntForOpen -= 1 else: cntForOpen += 1 # If count of open brackets # becomes less than 0 if (cntForOpen < 0): check = 0 break if (check and cntForOpen == 0): print("Yes, ", end="") # Print the new string for i in range(n): if (str[i] == str[n - 1]): print(')', end="") else: print('(', end="") return else: for i in range(n): # If the current character is # same as the first character if (str[i] == str[0]): cntForClose += 1 else: cntForClose -= 1 # If bracket sequence # is not balanced if (cntForClose < 0): check = 0 break # Check for unbalanced # bracket sequence if (check and cntForClose == 0): print("Yes, ", end="") # Print the sequence for i in range(n): if (str[i] == str[0]): print('(', end="") else: print(')', end="") return print("NO", end="") # Driver Code # Given Input str = "123122" # Function Call balBracketSequence(str) # This code is contributed by gfgking
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to check if the given // string can be converted to a // balanced bracket sequence or not static void balBracketSequence(string str) { int n = str.Length; // Check if the first and // last characters are equal if (str[0] == str[n - 1]) { Console.Write("No"); } else { // Initialize two variables to store // the count of open and closed brackets int cntForOpen = 0, cntForClose = 0; int check = 1; for(int i = 0; i < n; i++) { // If the current character is // same as the first character if (str[i] == str[0]) cntForOpen++; // If the current character is // same as the last character else if (str[i] == str[n - 1]) cntForOpen--; else cntForOpen++; // If count of open brackets // becomes less than 0 if (cntForOpen < 0) { check = 0; break; } } if (check != 0 && cntForOpen == 0) { Console.Write("Yes, "); // Print the new string for(int i = 0; i < n; i++) { if (str[i] == str[n - 1]) Console.Write(')'); else Console.Write('('); } return; } else { for(int i = 0; i < n; i++) { // If the current character is // same as the first character if (str[i] == str[0]) cntForClose++; else cntForClose--; // If bracket sequence // is not balanced if (cntForClose < 0) { check = 0; break; } } // Check for unbalanced // bracket sequence if (check != 0 && cntForClose == 0) { Console.Write("Yes, "); // Print the sequence for(int i = 0; i < n; i++) { if (str[i] == str[0]) Console.Write('('); else Console.Write(')'); } return; } } Console.Write("No"); } } // Driver Code public static void Main() { // Given Input string str = "123122"; // Function Call balBracketSequence(str); } } // This code is contributed by sanjoy_62
Javascript
<script> // JavaScript program for the above approach; // Function to check if the given // string can be converted to a // balanced bracket sequence or not function balBracketSequence(str) { let n = str.length; // Check if the first and // last characters are equal if (str[0] == str[n - 1]) { document.write( "No"); } else { // Initialize two variables to store // the count of open and closed brackets let cntForOpen = 0, cntForClose = 0; let check = 1; for (let i = 0; i < n; i++) { // If the current character is // same as the first character if (str[i] == str[0]) cntForOpen++; // If the current character is // same as the last character else if (str[i] == str[n - 1]) cntForOpen--; else cntForOpen++; // If count of open brackets // becomes less than 0 if (cntForOpen < 0) { check = 0; break; } } if (check && cntForOpen == 0) { document.write("Yes, "); // Print the new string for (let i = 0; i < n; i++) { if (str[i] == str[n - 1]) document.write(')'); else document.write('('); } return; } else { for (let i = 0; i < n; i++) { // If the current character is // same as the first character if (str[i] == str[0]) cntForClose++; else cntForClose--; // If bracket sequence // is not balanced if (cntForClose < 0) { check = 0; break; } } // Check for unbalanced // bracket sequence if (check && cntForClose == 0) { document.write("Yes, "); // Print the sequence for (let i = 0; i < n; i++) { if (str[i] == str[0]) document.write('('); else document.write(')'); } return; } } document.write("NO") ; } } // Driver Code // Given Input let str = "123122"; // Function Call balBracketSequence(str); // This code is contributed by Potta Lokesh </script>
Yes,()(())
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ramashishkushwaha819 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA