Dada una expresión con solo ‘}’ y ‘{‘. La expresión puede no estar equilibrada. Encuentre el número mínimo de inversiones de paréntesis para equilibrar la expresión.
Ejemplos:
Input: exp = "}{"
Output: 2
We need to change '}' to '{' and '{' to
'}' so that the expression becomes balanced,
the balanced expression is '{}'
Input: exp = "{{{"
Output: Can't be made balanced using reversals
Input: exp = "{{{{"
Output: 2
Input: exp = "{{{{}}"
Output: 1
Input: exp = "}{{}}{{{"
Output: 3
Una observación simple es que la string se puede equilibrar solo si el número total de paréntesis es par (debe haber el mismo número de ‘{‘ y ‘}’)
Una solución ingenua es considerar cada paréntesis y contar recursivamente el número de inversiones tomando dos casos (i) manteniendo el soporte como está (ii) invirtiendo el soporte. Si obtenemos una expresión equilibrada, actualizamos el resultado si el número de pasos seguidos para llegar aquí es menor que el mínimo hasta el momento. La complejidad temporal de esta solución es O(2 n ).
Una Solución Eficiente puede resolver este problema en tiempo O(n). La idea es eliminar primero toda la parte equilibrada de la expresión. Por ejemplo, convierta «} {{}} {{{» a «}{{{» eliminando la parte resaltada. Si miramos más de cerca, podemos notar que, después de eliminar la parte balanceada, siempre terminamos con una expresión de la forma }}…}{{…{, una expresión que contiene 0 o más corchetes de cierre seguidos de 0 o más números de paréntesis de apertura.
¿Cuántas reversiones mínimas se requieren para una expresión de la forma “}}..}{{..{” ?. Sea m el número total de corchetes de cierre y n el número de corchetes de apertura. Necesitamos inversiones de ⌈m/2⌉ + ⌈n/2⌉. Por ejemplo, }}}}{{ requiere 2+1 reversiones.
A continuación se muestra la implementación de la idea anterior:
C++14
// C++ program to find minimum number of
// reversals required to balance an expression
#include <bits/stdc++.h>
using namespace std;
// Returns count of minimum reversals for making
// expr balanced. Returns -1 if expr cannot be
// balanced.
int countMinReversals(string expr)
{
int len = expr.length();
// length of expression must be even to make
// it balanced by using reversals.
if (len % 2)
return -1;
// After this loop, stack contains unbalanced
// part of expression, i.e., expression of the
// form "}}..}{{..{"
stack<char> s;
for (int i = 0; i < len; i++) {
if (expr[i] == '}' && !s.empty()) {
if (s.top() == '{')
s.pop();
else
s.push(expr[i]);
}
else
s.push(expr[i]);
}
// Length of the reduced expression
// red_len = (m+n)
int red_len = s.size();
// count opening brackets at the end of
// stack
int n = 0;
while (!s.empty() && s.top() == '{') {
s.pop();
n++;
}
// return ceil(m/2) + ceil(n/2) which is
// actually equal to (m+n)/2 + n%2 when
// m+n is even.
return (red_len / 2 + n % 2);
}
// Driver program to test above function
int main()
{
string expr = "}}{{";
cout << countMinReversals(expr);
return 0;
}
Java
// Java Code to count minimum reversal for
// making an expression balanced.
import java.util.Stack;
public class GFG {
// Method count minimum reversal for
// making an expression balanced.
// Returns -1 if expression cannot be balanced
static int countMinReversals(String expr)
{
int len = expr.length();
// length of expression must be even to make
// it balanced by using reversals.
if (len % 2 != 0)
return -1;
// After this loop, stack contains unbalanced
// part of expression, i.e., expression of the
// form "}}..}{{..{"
Stack<Character> s = new Stack<>();
for (int i = 0; i < len; i++) {
char c = expr.charAt(i);
if (c == '}' && !s.empty()) {
if (s.peek() == '{')
s.pop();
else
s.push(c);
}
else
s.push(c);
}
// Length of the reduced expression
// red_len = (m+n)
int red_len = s.size();
// count opening brackets at the end of
// stack
int n = 0;
while (!s.empty() && s.peek() == '{') {
s.pop();
n++;
}
// return ceil(m/2) + ceil(n/2) which is
// actually equal to (m+n)/2 + n%2 when
// m+n is even.
return (red_len / 2 + n % 2);
}
// Driver method
public static void main(String[] args)
{
String expr = "}}{{";
System.out.println(countMinReversals(expr));
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python3 program to find minimum number of
# reversals required to balance an expression
# Returns count of minimum reversals
# for making expr balanced. Returns -1
# if expr cannot be balanced.
def countMinReversals(expr):
lenn = len(expr)
# length of expression must be even
# to make it balanced by using reversals.
if (lenn % 2):
return -1
# After this loop, stack contains
# unbalanced part of expression,
# i.e., expression of the form "...."
s = []
for i in range(lenn):
if (expr[i] == '}' and len(s)):
if (s[0] == '{'):
s.pop(0)
else:
s.insert(0, expr[i])
else:
s.insert(0, expr[i])
# Length of the reduced expression
# red_len = (m+n)
red_len = len(s)
# count opening brackets at the
# end of stack
n = 0
while (len(s)and s[0] == '{'):
s.pop(0)
n += 1
# return ceil(m/2) + ceil(n/2) which
# is actually equal to (m+n)/2 + n%2
# when m+n is even.
return (red_len // 2 + n % 2)
# Driver Code
if __name__ == '__main__':
expr = "}{"
print(countMinReversals(expr.strip()))
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# Code to count minimum reversal for
// making an expression balanced.
using System;
using System.Collections.Generic;
class GFG {
// Method count minimum reversal for
// making an expression balanced.
// Returns -1 if expression cannot be balanced
public static int countMinReversals(string expr)
{
int len = expr.Length;
// length of expression must be
// even to make it balanced by
// using reversals.
if (len % 2 != 0) {
return -1;
}
// After this loop, stack contains
// unbalanced part of expression,
// i.e., expression of the form "}}..}{{..{"
Stack<char> s = new Stack<char>();
for (int i = 0; i < len; i++) {
char c = expr[i];
if (c == '}' && s.Count > 0) {
if (s.Peek() == '{') {
s.Pop();
}
else {
s.Push(c);
}
}
else {
s.Push(c);
}
}
// Length of the reduced expression
// red_len = (m+n)
int red_len = s.Count;
// count opening brackets at
// the end of stack
int n = 0;
while (s.Count > 0 && s.Peek() == '{') {
s.Pop();
n++;
}
// return ceil(m/2) + ceil(n/2) which is
// actually equal to (m+n)/2 + n%2 when
// m+n is even.
return (red_len / 2 + n % 2);
}
// Driver Code
public static void Main(string[] args)
{
string expr = "}}{{";
Console.WriteLine(countMinReversals(expr));
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// JavaScript program to find minimum number of
// reversals required to balance an expression
// Returns count of minimum reversals for making
// expr balanced. Returns -1 if expr cannot be
// balanced.
function countMinReversals(expr) {
let len = expr.length;
// Expressions of odd lengths
// cannot be balanced
if (len % 2)
return -1;
// After this loop, stack contains unbalanced
// part of expression, i.e., expression of the
// form "}}..}{{..{"
var s = new Array();
for (let i = 0; i < len; i++) {
if (expr[i] == '}' && !s.length == 0) {
if (s[s.length - 1] == '{')
s.pop();
else
s.push(expr[i]);
}
else
s.push(expr[i]);
}
// Length of the reduced expression
// red_len = (m+n)
let red_len = s.length;
// count opening brackets at the end of
// stack
let n = 0;
while (!s.length == 0 && s[s.length - 1] == '{') {
s.pop();
n++;
}
// return ceil(m/2) + ceil(n/2) which is
// actually equal to (m+n)/2 + n%2 when
// m+n is even.
return (red_len / 2 + n % 2);
}
// Driver program to test above function
let expr = "}}{{";
document.write(countMinReversals(expr));
</script>
Producción
2
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Otra solución intuitiva puede resolver este problema con la misma complejidad.
La idea es seguir el algoritmo utilizado en Comprobar si el paréntesis está equilibrado o no. Seguimos este algoritmo con una nueva condición cuando encontramos que el paréntesis no está balanceado. Este caso surge cuando la pila está vacía y nos encontramos con un ‘ } ‘. En el programa Comprobar si el paréntesis está equilibrado o no , rompemos el ciclo cuando encontramos que el paréntesis no está equilibrado, pero aquí lo invertiremos a ‘ { ‘ y lo empujaremos a la pila. Al hacer esto, la respuesta se incrementa en 1.
Aquí, dado que encontramos un caso de expresión desequilibrada, el ‘ { ‘ debe cambiarse para obtener una expresión equilibrada. Además, cambiar esto sería la forma más mínima de obtener una expresión equilibrada, ya que es una condición imprescindible para cambiarla.
Por ejemplo, string = “}{{}}{}}” se convertirá en “ { {{}}{}}” y obtendremos una expresión equilibrada. Puede surgir un caso en el que después de hacer esto a la string nos quede algo de ‘{‘ en la pila. Por ejemplo, string = “{}{{{{”” se convertirá en “{} {{{{ ” y habrá 4 ‘{‘ presentes en la pila que no se extraen ni se equilibran.
Simplemente podemos equilibrarlo invirtiendo la mitad derecha de la pila a ‘}’. Ejemplo: si a la pila le queda ‘ {{{{ ‘, lo convertimos en ‘ {{ }} ‘ formando una expresión balanceada. Por lo tanto, la respuesta se actualiza por (tamaño de pila / 2). En el caso de que el tamaño de la pila sea impar, no es posible transformarlo en una string equilibrada.
A continuación se muestra la implementación de la idea anterior:
C++
#include <iostream>
using namespace std;
#include <stack>
int countMinReversals(string str)
{
// Step 1: Initialize a stack of char type and ans as 0.
stack<char> st;
int ans = 0;
// Step 2: Run a loop for each character of the string
for (int i = 0; i < str.size(); i++) {
// Step 2.1: If ' { ' encountered push it to the
// stack
if (str[i] == '{')
st.push(str[i]);
// Step 2.2: If ' } ' is encountered
else {
// Step 2.2.1: If stack has a '{' present for
// '}' encountered, pop from the stack.
if (!st.empty())
st.pop();
// Step 2.2.2: If stack is empty, change '}' to
// '{' and push it to stack and increment ans by
// 1
else {
st.push('{');
ans++;
}
}
}
// Step 3: if stack size is odd return -1.
if (st.size() % 2 != 0)
return -1;
// Step 4: Increment ans by ( stackSize/2 ).
ans += st.size() / 2;
return ans;
}
int main()
{
string expr = "{{{{}}";
cout << countMinReversals(expr);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.Stack;
class GFG {
static int countMinReversals(String str)
{
// Step 1: Initialize a stack of char type and ans as 0.
Stack<Character> st = new Stack<Character>();
int ans = 0;
// Step 2: Run a loop for each character of the string
for (int i = 0; i < str.length(); i++) {
// Step 2.1: If ' { ' encountered push it to the
// stack
if (str.charAt(i) == '{')
st.add(str.charAt(i));
// Step 2.2: If ' } ' is encountered
else {
// Step 2.2.1: If stack has a '{' present for
// '}' encountered, pop from the stack.
if (!st.isEmpty())
st.pop();
// Step 2.2.2: If stack is empty, change '}' to
// '{' and push it to stack and increment ans by
// 1
else {
st.add('{');
ans++;
}
}
}
// Step 3: if stack size is odd return -1.
if (st.size() % 2 != 0)
return -1;
// Step 4: Increment ans by ( stackSize/2 ).
ans += st.size() / 2;
return ans;
}
// Driver code
public static void main(String args[])
{
String expr = "{{{{}}";
System.out.println(countMinReversals(expr));
}
}
// This code iscontributed by shinjanpatra.
Python3
# Python code to implement the approach
def countMinReversals(Str):
# Step 1: Initialize a stack of char type and ans as 0.
st = []
ans = 0
# Step 2: Run a loop for each character of the String
for i in range(len(Str)):
# Step 2.1: If ' { ' encountered push it to the
# stack
if (Str[i] == '{'):
st.append(Str[i])
# Step 2.2: If ' } ' is encountered
else:
# Step 2.2.1: If stack has a '{' present for
# '}' encountered, pop from the stack.
if (len(st)>0):
st.pop()
# Step 2.2.2: If stack is empty, change '}' to
# '{' and push it to stack and increment ans by
# 1
else:
st.push('{')
ans += 1
# Step 3: if stack size is odd return -1.
if (len(st) % 2 != 0):
return -1
# Step 4: Increment ans by ( stackSize/2 ).
ans += len(st) // 2
return ans
# driver code
expr = "{{{{}}"
print(countMinReversals(expr))
# This code is contributed by shinjanpatra
C#
// C# Code to count minimum reversal for
// making an expression balanced.
using System;
using System.Collections.Generic;
class GFG
{
public static int countMinReversals(string str)
{
// Step 1: Initialize a stack of char type and ans as 0.
Stack<char> st = new Stack<char>();
int ans = 0;
// Step 2: Run a loop for each character of the string
for (int i = 0; i < str.Length; i++)
{
// Step 2.1: If ' { ' encountered push it to the
// stack
if (str[i] == '{')
st.Push(str[i]);
// Step 2.2: If ' } ' is encountered
else
{
// Step 2.2.1: If stack has a '{' present for
// '}' encountered, pop from the stack.
if (st.Count > 0)
st.Pop();
// Step 2.2.2: If stack is empty, change '}' to
// '{' and push it to stack and increment ans by
// 1
else
{
st.Push('{');
ans++;
}
}
}
// Step 3: if stack size is odd return -1.
if (st.Count % 2 != 0)
return -1;
// Step 4: Increment ans by ( stackSize/2 ).
ans += st.Count / 2;
return ans;
}
// Driver Code
public static void Main(string[] args)
{
string expr = "{{{{}}";
Console.WriteLine(countMinReversals(expr));
}
}
// This code is contributed by kothavvsaakash
Javascript
<script>
// JavaScript code to implement the approach
function countMinReversals(Str){
// Step 1: Initialize a stack of char type and ans as 0.
let st = []
let ans = 0
// Step 2: Run a loop for each character of the String
for(let i=0;i<Str.length;i++){
// Step 2.1: If ' { ' encountered push it to the
// stack
if (Str[i] == '{')
st.push(Str[i])
// Step 2.2: If ' } ' is encountered
else{
// Step 2.2.1: If stack has a '{' present for
// '}' encountered, pop from the stack.
if (st.length>0)
st.pop()
// Step 2.2.2: If stack is empty, change '}' to
// '{' and push it to stack and increment ans by
// 1
else{
st.push('{')
ans += 1
}
}
}
// Step 3: if stack size is odd return -1.
if (st.length % 2 != 0)
return -1
// Step 4: Increment ans by ( stackSize/2 ).
ans += st.length / 2
return ans
}
// driver code
let expr = "{{{{}}"
document.write(countMinReversals(expr),"</br>")
// This code is contributed by shinjanpatra
</script>
Producción:
1
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(n)
Otra solución eficiente resuelve el problema en O(1), es decir, espacio constante. Dado que la expresión solo contiene un tipo de corchetes, la idea es mantener dos variables para llevar la cuenta del corchete izquierdo y del corchete derecho como hicimos en Longitud de la substring válida más larga . Si la expresión tiene paréntesis equilibrados, entonces decrementamos la variable izquierda; de lo contrario, incrementamos la variable derecha. Entonces todo lo que necesitamos para regresar es ceil(left/2) + ceil(right/2).
C++
// C++ program to find minimum number of
// reversals required to balance an expression
#include <bits/stdc++.h>
using namespace std;
// Returns count of minimum reversals for making
// expr balanced. Returns -1 if expr cannot be
// balanced.
int countMinReversals(string expr)
{
int len = expr.length();
// Expressions of odd lengths
// cannot be balanced
if (len % 2 != 0) {
return -1;
}
int left_brace = 0, right_brace = 0;
int ans;
for (int i = 0; i < len; i++) {
// If we find a left bracket then we simply
// increment the left bracket
if (expr[i] == '{') {
left_brace++;
}
// Else if left bracket is 0 then we find
// unbalanced right bracket and increment
// right bracket or if the expression
// is balanced then we decrement left
else {
if (left_brace == 0) {
right_brace++;
}
else {
left_brace--;
}
}
}
ans = ceil(left_brace / 2.0) + ceil(right_brace / 2.0);
return ans;
}
// Driver program to test above function
int main()
{
string expr = "}}{{";
cout << countMinReversals(expr);
return 0;
}
Java
// Java Code to count minimum reversal for
// making an expression balanced.
import java.util.*;
public class GFG {
// Method count minimum reversal for
// making an expression balanced.
// Returns -1 if expression cannot be balanced
static int countMinReversals(String expr)
{
int len = expr.length();
int ans;
// Expressions of odd lengths
// cannot be balanced
if (len % 2 != 0) {
return -1;
}
int left_brace = 0, right_brace = 0;
for (int i = 0; i < len; i++) {
char ch = expr.charAt(i);
// If we find a left bracket then we simply
// increment the left bracket
if (ch == '{') {
left_brace++;
}
// Else if left bracket is 0 then we find
// unbalanced right bracket and increment
// right bracket or if the expression
// is balanced then we decrement left
else {
if (left_brace == 0) {
right_brace++;
}
else {
left_brace--;
}
}
}
ans = (int)(Math.ceil((0.0 + left_brace) / 2)
+ Math.ceil((0.0 + right_brace) / 2));
return ans;
}
// Driver method
public static void main(String[] args)
{
String expr = "}}{{";
System.out.println(countMinReversals(expr));
}
}
Python3
# Python 3 program to find minimum number of
# reversals required to balance an expression
import math
# Returns count of minimum reversals for making
# expr balanced. Returns -1 if expr cannot be
# balanced.
def countMinReversals(expr):
length = len(expr)
# Expressions of odd lengths
# cannot be balanced
if (length % 2 != 0):
return -1
left_brace = 0
right_brace = 0
for i in range(length):
# If we find a left bracket then we simply
# increment the left bracket
if (expr[i] == '{'):
left_brace += 1
# Else if left bracket is 0 then we find
# unbalanced right bracket and increment
# right bracket or if the expression
# is balanced then we decrement left
else:
if (left_brace == 0):
right_brace += 1
else:
left_brace -= 1
ans = math.ceil(left_brace / 2) + math.ceil(right_brace / 2)
return ans
# Driver program to test above function
if __name__ == "__main__":
expr = "}}{{"
print(countMinReversals(expr))
# This code is contributed by ukasp.
C#
// C# Code to count minimum reversal for
// making an expression balanced.
using System;
public class GFG {
// Method count minimum reversal for
// making an expression balanced.
// Returns -1 if expression cannot be balanced
static int countMinReversals(String expr)
{
int len = expr.Length;
int ans;
// Expressions of odd lengths
// cannot be balanced
if (len % 2 != 0) {
return -1;
}
int left_brace = 0, right_brace = 0;
for (int i = 0; i < len; i++) {
char ch = expr[i];
// If we find a left bracket then we simply
// increment the left bracket
if (ch == '{') {
left_brace++;
}
// Else if left bracket is 0 then we find
// unbalanced right bracket and increment
// right bracket or if the expression
// is balanced then we decrement left
else {
if (left_brace == 0) {
right_brace++;
}
else {
left_brace--;
}
}
}
ans = (int)(Math.Ceiling((0.0 + left_brace) / 2)
+ Math.Ceiling((0.0 + right_brace)
/ 2));
return ans;
}
// Driver method
public static void Main(String[] args)
{
String expr = "}}{{";
Console.WriteLine(countMinReversals(expr));
}
}
// This code is contributed by aashish1995.
Javascript
<script>
// JavaScript program to find minimum number of
// reversals required to balance an expression
// Returns count of minimum reversals for making
// expr balanced. Returns -1 if expr cannot be
// balanced.
function countMinReversals( expr)
{
let len = expr.length;
// Expressions of odd lengths
// cannot be balanced
if (len % 2 != 0) {
return -1;
}
let left_brace = 0, right_brace = 0;
let ans;
for (let i = 0; i < len; i++) {
// If we find a left bracket then we simply
// increment the left bracket
if (expr[i] == '{') {
left_brace++;
}
// Else if left bracket is 0 then we find
// unbalanced right bracket and increment
// right bracket or if the expression
// is balanced then we decrement left
else {
if (left_brace == 0) {
right_brace++;
}
else {
left_brace--;
}
}
}
ans = Math.ceil(left_brace / 2) + Math.ceil(right_brace / 2);
return ans;
}
// Driver program to test above function
let expr = "}}{{";
document.write(countMinReversals(expr));
</script>
Producción
2
Complejidad de tiempo : O(n)
Espacio Auxiliar : O(1)
En lugar de mantener dos variables diferentes para la llave izquierda y la llave derecha, podemos hacerlo usando una única variable temporal.
Atraviesa la array. Para cada ‘{‘ , incremente el valor de temp en 1 y para cada ‘}’, si el valor de temp > 0, luego disminuya el valor de temp en 1, de lo contrario, incremente el valor de resultado y temp en 1. En end, agregue la mitad del valor de temp al resultado.
A continuación se muestra la implementación del enfoque anterior en C++.
C++
// C++ program to find minimum number of
// reversals required to balance an expression
#include <bits/stdc++.h>
using namespace std;
// Returns count of minimum reversals for making
// expr balanced. Returns -1 if expr cannot be
// balanced.
int countMinReversals(string s)
{
int temp = 0, res = 0, n = s.size();
if (n % 2 != 0)
return -1;
for (int i = 0; i < n; i++) {
if (s[i] == '{')
temp++;
else {
if (temp == 0) {
res++;
temp++;
}
else
temp--;
}
}
if (temp > 0)
res += temp / 2;
return res;
}
// Driver program to test above function
int main()
{
string expr = "}}{{";
cout << countMinReversals(expr);
return 0;
// This code is contributed by Akansha Mittal
}
Java
// Java program to find minimum number of
// reversals required to balance an expression
import java.util.*;
class GFG {
// Returns count of minimum reversals for making
// expr balanced. Returns -1 if expr cannot be
// balanced.
static int countMinReversals(String s)
{
int temp = 0, res = 0, n = s.length();
if (n % 2 != 0)
return -1;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '{')
temp++;
else {
if (temp == 0) {
res++;
temp++;
}
else
temp--;
}
}
if (temp > 0)
res += temp / 2;
return res;
}
// Driver program to test above function
public static void main(String[] args)
{
String expr = "}}{{";
System.out.print(countMinReversals(expr));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python program to find minimum number of
# reversals required to balance an expression
# Returns count of minimum reversals for making
# expr balanced. Returns -1 if expr cannot be
# balanced.
def countMinReversals(s):
temp, res, n = 0, 0, len(s)
if (n % 2 != 0):
return -1
for i in range(n):
if (s[i] == '{'):
temp += 1
else:
if (temp == 0):
res += 1
temp += 1
else:
temp -= 1
if (temp > 0):
res += temp // 2
return res
# Driver program to test above function
expr = "}}{{"
print(countMinReversals(expr))
# This code is contributed by shinjanpatra
C#
// C# program to find minimum number of
// reversals required to balance an expression
using System;
class GFG {
// Returns count of minimum reversals for making
// expr balanced. Returns -1 if expr cannot be
// balanced.
static int countMinReversals(string s)
{
int temp = 0, res = 0, n = s.Length;
if (n % 2 != 0)
return -1;
for (int i = 0; i < n; i++) {
if (s[i] == '{')
temp++;
else {
if (temp == 0) {
res++;
temp++;
}
else
temp--;
}
}
if (temp > 0)
res += temp / 2;
return res;
}
// Driver program to test above function
public static void Main()
{
string expr = "}}{{";
Console.Write(countMinReversals(expr));
}
}
// This code is contribute by ukasp.
Javascript
<script>
// javascript program to find minimum number of
// reversals required to balance an expression
// Returns count of minimum reversals for making
// expr balanced. Returns -1 if expr cannot be
// balanced.
function countMinReversals( s)
{
var temp = 0, res = 0, n = s.length;
if (n % 2 != 0)
return -1;
for (i = 0; i < n; i++) {
if (s.charAt(i) == '{')
temp++;
else {
if (temp == 0) {
res++;
temp++;
} else
temp--;
}
}
if (temp > 0)
res += temp / 2;
return res;
}
// Driver program to test above function
var expr = "}}{{";
document.write(countMinReversals(expr));
// This code is contributed by Rajput-Ji
</script>
Producción
2
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Gracias a Utkarsh Trivedi por sugerir el enfoque anterior.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA