Dada una string S de tamaño N que consiste solo en ‘(‘ y ‘)’ y un entero positivo K , la tarea es verificar si la string dada puede convertirse en una secuencia de paréntesis válida moviendo cualquier carácter de la string S a cualquiera final de la string como máximo K número de veces.
Ejemplos:
Entrada: S = «)(«, K = 1
Salida: Sí
Explicación: Mueva S[0] al final de la string.
Ahora, la string S modificada es «()», que está balanceada. Por lo tanto, el número de movimientos requerido es 1( = K).Entrada: S = “()()”, K = 0
Salida: Sí
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Si N es impar o el recuento de paréntesis de apertura y cierre no es igual, entonces no es posible hacer una secuencia de paréntesis válida.
- La idea es recorrer la secuencia dada y realizar un seguimiento de la diferencia de conteo de paréntesis de apertura y cierre, y si la diferencia se vuelve negativa en cualquier índice, entonces mueva algún paréntesis de apertura después del índice actual y muévalo al principio.
Siga los pasos a continuación para resolver el problema:
- Si N es impar o el recuento de paréntesis de apertura y cierre no es igual, entonces no es posible hacer una secuencia de paréntesis válida. Por lo tanto, escriba «No» . De lo contrario, realice los siguientes pasos:
- Inicialice dos variables, digamos count y ans como 0 que realiza un seguimiento de la diferencia de paréntesis de apertura y cierre y el número requerido de movimientos respectivamente.
- Atraviese la string S dada y realice los siguientes pasos:
- Si el carácter actual S[i] es ‘ ( ‘, incremente el valor de count en 1 .
- De lo contrario, disminuya el valor de count en 1 .
- Si el recuento es inferior a 0 , actualice el recuento a 0 e incremente el valor de ans en 1 .
- Después de completar los pasos anteriores, si el valor de ans es como máximo K , imprima «Sí» . De lo contrario, escriba “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if a valid parenthesis
// can be obtained by moving characters
// to either end at most K number of times
void minimumMoves(string s, int n, int k)
{
// Base Case 1
if (n & 1) {
cout << "No";
return;
}
// Count of '(' and ')'
int countOpen = count(s.begin(),
s.end(), '(');
int countClose = count(s.begin(),
s.end(), ')');
// Base Case 2
if (countOpen != countClose) {
cout << "No";
return;
}
// Store the count of moves required
// to make a valid parenthesis
int ans = 0;
int cnt = 0;
// Traverse the string
for (int i = 0; i < n; ++i) {
// Increment cnt if opening
// bracket has occurred
if (s[i] == '(')
++cnt;
// Otherwise, decrement cnt by 1
else {
// Decrement cnt by 1
--cnt;
// If cnt is negative
if (cnt < 0) {
// Update the cnt
cnt = 0;
// Increment the ans
++ans;
}
}
}
// If ans is at most K, then
// print Yes. Otherwise print No
if (ans <= k)
cout << "Yes";
else
cout << "No";
}
// Driver Code
int main()
{
string S = ")(";
int K = 1;
minimumMoves(S, S.length(), K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to check if a valid parenthesis
// can be obtained by moving characters
// to either end at most K number of times
static void minimumMoves(String s, int n, int k)
{
// Base Case 1
if (n % 2 == 1)
{
System.out.println("No");
return;
}
// Count of '(' and ')'
int countOpen = 0, countClose = 0;
for(char ch : s.toCharArray())
if (ch == '(')
countOpen++;
else if (ch == ')')
countClose++;
// Base Case 2
if (countOpen != countClose)
{
System.out.println("No");
return;
}
// Store the count of moves required
// to make a valid parenthesis
int ans = 0;
int cnt = 0;
// Traverse the string
for(int i = 0; i < n; ++i)
{
// Increment cnt if opening
// bracket has occurred
if (s.charAt(i) == '(')
++cnt;
// Otherwise, decrement cnt by 1
else
{
// Decrement cnt by 1
--cnt;
// If cnt is negative
if (cnt < 0)
{
// Update the cnt
cnt = 0;
// Increment the ans
++ans;
}
}
}
// If ans is at most K, then
// print Yes. Otherwise print No
if (ans <= k)
System.out.println("Yes");
else
System.out.println("No");
}
// Driver Code
public static void main(String[] args)
{
String S = ")(";
int K = 1;
minimumMoves(S, S.length(), K);
}
}
// This code is contributed by Kingash
Python3
# python 3 program for the above approach
# Function to check if a valid parenthesis
# can be obtained by moving characters
# to either end at most K number of times
def minimumMoves(s, n, k):
# Base Case 1
if (n & 1):
print("No")
return
# Count of '(' and ')'
countOpen = s.count('(')
countClose = s.count(')')
# Base Case 2
if (countOpen != countClose):
print("No")
return
# Store the count of moves required
# to make a valid parenthesis
ans = 0
cnt = 0
# Traverse the string
for i in range(n):
# Increment cnt if opening
# bracket has occurred
if (s[i] == '('):
cnt += 1
# Otherwise, decrement cnt by 1
else:
# Decrement cnt by 1
cnt -= 1
# If cnt is negative
if (cnt < 0):
# Update the cnt
cnt = 0
# Increment the ans
ans += 1
# If ans is at most K, then
# print Yes. Otherwise print No
if (ans <= k):
print("Yes")
else:
print("No")
# Driver Code
if __name__ == "__main__":
S = ")("
K = 1
minimumMoves(S, len(S), K)
# This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if a valid parenthesis
// can be obtained by moving characters
// to either end at most K number of times
static void minimumMoves(string s, int n, int k)
{
// Base Case 1
if (n % 2 == 1)
{
Console.WriteLine("No");
return;
}
// Count of '(' and ')'
int countOpen = 0, countClose = 0;
foreach(char ch in s.ToCharArray())
if (ch == '(')
countOpen++;
else if (ch == ')')
countClose++;
// Base Case 2
if (countOpen != countClose)
{
Console.WriteLine("No");
return;
}
// Store the count of moves required
// to make a valid parenthesis
int ans = 0;
int cnt = 0;
// Traverse the string
for(int i = 0; i < n; ++i)
{
// Increment cnt if opening
// bracket has occurred
if (s[i] == '(')
++cnt;
// Otherwise, decrement cnt by 1
else
{
// Decrement cnt by 1
--cnt;
// If cnt is negative
if (cnt < 0)
{
// Update the cnt
cnt = 0;
// Increment the ans
++ans;
}
}
}
// If ans is at most K, then
// print Yes. Otherwise print No
if (ans <= k)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
// Driver Code
static void Main()
{
string S = ")(";
int K = 1;
minimumMoves(S, S.Length, K);
}
}
// This code is contributed by SoumikMondal
Javascript
<script>
// JavaScript program for the above approach
// Function to check if a valid parenthesis
// can be obtained by moving characters
// to either end at most K number of times
function minimumMoves(s,n,k)
{
// Base Case 1
if (n & 1) {
document.write("No");
return;
}
// Count of '(' and ')'
var countOpen = 0;
var i;
for(i=0;i<s.length;i++){
if(s[i]=="(")
countOpen++;
}
var countClose = 0;
for(i=0;i<s.length;i++){
if(s[i]==")")
countClose++;
};
// Base Case 2
if (countOpen != countClose) {
document.write("No");
return;
}
// Store the count of moves required
// to make a valid parenthesis
var ans = 0;
var cnt = 0;
// Traverse the string
for (i = 0; i < n; ++i) {
// Increment cnt if opening
// bracket has occurred
if (s[i] == '(')
++cnt;
// Otherwise, decrement cnt by 1
else {
// Decrement cnt by 1
--cnt;
// If cnt is negative
if (cnt < 0) {
// Update the cnt
cnt = 0;
// Increment the ans
++ans;
}
}
}
// If ans is at most K, then
// print Yes. Otherwise print No
if (ans <= k)
document.write("Yes");
else
document.write("No");
}
// Driver Code
var S = ")(";
var K = 1;
minimumMoves(S, S.length, K);
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA