Se le da una string de 2N caracteres que consta de N corchetes ‘[‘ y N corchetes ‘]’. Una string se considera balanceada si puede representarse en la forma S2[S1] donde S1 y S2 son strings balanceadas. Podemos hacer que una string no balanceada sea balanceada intercambiando caracteres adyacentes. Calcule el número mínimo de intercambios necesarios para equilibrar una string.
Ejemplos:
Input : []][][ Output : 2 First swap: Position 3 and 4 [][]][ Second swap: Position 5 and 6 [][][] Input : [[][]] Output : 0 The string is already balanced.
Podemos resolver este problema usando estrategias codiciosas. Si los primeros caracteres X forman una string equilibrada, podemos ignorar estos caracteres y continuar. Si encontramos un ‘]’ antes del ‘[‘ requerido, entonces debemos comenzar a intercambiar elementos para equilibrar la string.
Enfoque ingenuo
Inicialice la suma = 0 donde la suma almacena el resultado. Revise la string manteniendo un recuento del número de corchetes ‘[‘ encontrados. Reduzca este recuento cuando encontremos un carácter ‘]’. Si el conteo llega a ser negativo, debemos comenzar a equilibrar la string.
Deje que el índice ‘i’ represente la posición en la que estamos. Ahora avanzamos al siguiente ‘[‘ en el índice j. Aumenta la suma en j – i. Mueva el ‘[‘ en la posición j, a la posición i, y mueva todos los demás caracteres a la derecha. Vuelva a establecer el conteo en 0 y continúe recorriendo la string. Al final, ‘sum’ tendrá el valor requerido.
Complejidad de tiempo = O(N^2)
Espacio extra = O(1)
Enfoque optimizado
Inicialmente, podemos recorrer la string y almacenar las posiciones de ‘[‘ en un vector, digamos ‘ pos ‘. Inicialice ‘p’ a 0. Usaremos p para atravesar el vector ‘pos’. De manera similar al enfoque ingenuo, mantenemos un recuento de los corchetes ‘[‘ encontrados. Cuando encontramos un ‘[‘, aumentamos el conteo y aumentamos ‘p’ en 1. Cuando encontramos un ‘]’, disminuimos el conteo. Si el conteo alguna vez se vuelve negativo, esto significa que debemos comenzar a intercambiar. El elemento pos[p] nos dice el índice del siguiente ‘[‘. Incrementamos la suma por pos[p] – i, donde i es el índice actual. Podemos intercambiar los elementos en el índice actual y pos[p] y restablecer el conteo a 0 e incrementar p para que pos[p] indique el siguiente ‘[‘.
Dado que hemos convertido un paso que era O(N) en el enfoque ingenuo, a un paso O(1), nuestra nueva complejidad de tiempo se reduce.
Complejidad de tiempo = O(N)
Espacio extra = O(N)
C++
// C++ program to count swaps required to balance string
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to calculate swaps required
long swapCount(string s)
{
// Keep track of '['
vector<int> pos;
for (int i = 0; i < s.length(); ++i)
if (s[i] == '[')
pos.push_back(i);
int count = 0; // To count number of encountered '['
int p = 0; // To track position of next '[' in pos
long sum = 0; // To store result
for (int i = 0; i < s.length(); ++i)
{
// Increment count and move p to next position
if (s[i] == '[')
{
++count;
++p;
}
else if (s[i] == ']')
--count;
// We have encountered an unbalanced part of string
if (count < 0)
{
// Increment sum by number of swaps required
// i.e. position of next '[' - current position
sum += pos[p] - i;
swap(s[i], s[pos[p]]);
++p;
// Reset count to 1
count = 1;
}
}
return sum;
}
// Driver code
int main()
{
string s = "[]][][";
cout << swapCount(s) << "\n";
s = "[[][]]";
cout << swapCount(s) << "\n";
return 0;
}
Java
// Java program to count swaps
// required to balance string
import java.util.*;
class GFG{
// Function to calculate swaps required
public static long swapCount(String s)
{
// Keep track of '['
Vector<Integer> pos = new Vector<Integer>();
for(int i = 0; i < s.length(); ++i)
if (s.charAt(i) == '[')
pos.add(i);
// To count number of encountered '['
int count = 0;
// To track position of next '[' in pos
int p = 0;
// To store result
long sum = 0;
char[] S = s.toCharArray();
for(int i = 0; i < s.length(); ++i)
{
// Increment count and move p
// to next position
if (S[i] == '[')
{
++count;
++p;
}
else if (S[i] == ']')
--count;
// We have encountered an
// unbalanced part of string
if (count < 0)
{
// Increment sum by number of
// swaps required i.e. position
// of next '[' - current position
sum += pos.get(p) - i;
char temp = S[i];
S[i] = S[pos.get(p)];
S[pos.get(p)] = temp;
++p;
// Reset count to 1
count = 1;
}
}
return sum;
}
// Driver code
public static void main(String[] args)
{
String s = "[]][][";
System.out.println(swapCount(s));
s = "[[][]]";
System.out.println(swapCount(s));
}
}
// This code is contributed by divyesh072019
Python3
# Python3 Program to count # swaps required to balance # string # Function to calculate # swaps required def swapCount(s): # Keep track of '[' pos = [] for i in range(len(s)): if(s[i] == '['): pos.append(i) # To count number # of encountered '[' count = 0 # To track position # of next '[' in pos p = 0 # To store result sum = 0 s = list(s) for i in range(len(s)): # Increment count and # move p to next position if(s[i] == '['): count += 1 p += 1 elif(s[i] == ']'): count -= 1 # We have encountered an # unbalanced part of string if(count < 0): # Increment sum by number # of swaps required # i.e. position of next # '[' - current position sum += pos[p] - i s[i], s[pos[p]] = (s[pos[p]], s[i]) p += 1 # Reset count to 1 count = 1 return sum # Driver code s = "[]][][" print(swapCount(s)) s = "[[][]]" print(swapCount(s)) # This code is contributed by avanitrachhadiya2155
C#
// C# program to count swaps
// required to balance string
using System.IO;
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function to calculate swaps required
static long swapCount(string s)
{
// Keep track of '['
List<int> pos = new List<int>();
for(int i = 0; i < s.Length; i++)
{
if (s[i] == '[')
{
pos.Add(i);
}
}
// To count number of encountered '['
int count = 0;
// To track position of next '[' in pos
int p = 0;
// To store result
long sum = 0;
char[] S = s.ToCharArray();
for(int i = 0; i < S.Length; i++)
{
// Increment count and move p
// to next position
if (S[i] == '[')
{
++count;
++p;
}
else if (S[i] == ']')
{
--count;
}
// We have encountered an
// unbalanced part of string
if (count < 0)
{
// Increment sum by number of
// swaps required i.e. position
// of next '[' - current position
sum += pos[p]-i;
char temp = S[i];
S[i] = S[pos[p]];
S[pos[p]] = temp;
++p;
// Reset count to 1
count = 1;
}
}
return sum;
}
// Driver code
static void Main()
{
string s = "[]][][";
Console.WriteLine(swapCount(s));
s = "[[][]]";
Console.WriteLine(swapCount(s));
}
}
// This code is contributed by rag2127
Javascript
<script>
// JavaScript program to count swaps
// required to balance string
// Function to calculate swaps required
function swapCount(s)
{
// Keep track of '['
let pos = [];
for(let i = 0; i < s.length; ++i)
if (s[i] == '[')
pos.push(i);
// To count number of encountered '['
let count = 0;
// To track position of next '[' in pos
let p = 0;
// To store result
let sum = 0;
let S = s.split('');
for(let i = 0; i < s.length; ++i)
{
// Increment count and move p
// to next position
if (S[i] == '[')
{
++count;
++p;
}
else if (S[i] == ']')
--count;
// We have encountered an
// unbalanced part of string
if (count < 0)
{
// Increment sum by number of
// swaps required i.e. position
// of next '[' - current position
sum += pos[p] - i;
let temp = S[i];
S[i] = S[pos[p]];
S[pos[p]] = temp;
++p;
// Reset count to 1
count = 1;
}
}
return sum;
}
// Driver Code
let s = "[]][][";
document.write(swapCount(s) + "<br/>");
s = "[[][]]";
document.write(swapCount(s));
</script>
Producción:
2 0
Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(1)
Otro Método:
Podemos prescindir de tener que almacenar las posiciones de ‘[‘.
A continuación se muestra la implementación:
C++
// C++ program to count swaps required
// to balance string
#include <bits/stdc++.h>
using namespace std;
long swapCount(string chars)
{
// Stores total number of Left and
// Right brackets encountered
int countLeft = 0, countRight = 0;
// swap stores the number of swaps
// required imbalance maintains
// the number of imbalance pair
int swap = 0 , imbalance = 0;
for(int i = 0; i < chars.length(); i++)
{
if (chars[i] == '[')
{
// Increment count of Left bracket
countLeft++;
if (imbalance > 0)
{
// swaps count is last swap count + total
// number imbalanced brackets
swap += imbalance;
// imbalance decremented by 1 as it solved
// only one imbalance of Left and Right
imbalance--;
}
}
else if(chars[i] == ']' )
{
// Increment count of Right bracket
countRight++;
// imbalance is reset to current difference
// between Left and Right brackets
imbalance = (countRight - countLeft);
}
}
return swap;
}
// Driver code
int main()
{
string s = "[]][][";
cout << swapCount(s) << endl;
s = "[[][]]";
cout << swapCount(s) << endl;
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java Program to count swaps required to balance string
public class BalanceParan
{
static long swapCount(String s)
{
char[] chars = s.toCharArray();
// stores total number of Left and Right
// brackets encountered
int countLeft = 0, countRight = 0;
// swap stores the number of swaps required
//imbalance maintains the number of imbalance pair
int swap = 0 , imbalance = 0;
for(int i =0; i< chars.length; i++)
{
if(chars[i] == '[')
{
// increment count of Left bracket
countLeft++;
if(imbalance > 0)
{
// swaps count is last swap count + total
// number imbalanced brackets
swap += imbalance;
// imbalance decremented by 1 as it solved
// only one imbalance of Left and Right
imbalance--;
}
} else if(chars[i] == ']' )
{
// increment count of Right bracket
countRight++;
// imbalance is reset to current difference
// between Left and Right brackets
imbalance = (countRight-countLeft);
}
}
return swap;
}
// Driver code
public static void main(String args[])
{
String s = "[]][][";
System.out.println(swapCount(s) );
s = "[[][]]";
System.out.println(swapCount(s) );
}
}
// This code is contributed by Janmejaya Das.
Python3
# Python3 program to count swaps required to # balance string def swapCount(s): # Swap stores the number of swaps # required imbalance maintains the # number of imbalance pair swap = 0 imbalance = 0; for i in s: if i == '[': # Decrement the imbalance imbalance -= 1 else: # Increment imbalance imbalance += 1 if imbalance > 0: swap += imbalance return swap # Driver code s = "[]][]["; print(swapCount(s)) s = "[[][]]"; print(swapCount(s)) # This code is contributed by Prateek Gupta and improved by Anvesh Govind Saxena
C#
// C# Program to count swaps required
// to balance string
using System;
class GFG
{
public static long swapCount(string s)
{
char[] chars = s.ToCharArray();
// stores the total number of Left and
// Right brackets encountered
int countLeft = 0, countRight = 0;
// swap stores the number of swaps
// required imbalance maintains the
// number of imbalance pair
int swap = 0, imbalance = 0;
for (int i = 0; i < chars.Length; i++)
{
if (chars[i] == '[')
{
// increment count of Left bracket
countLeft++;
if (imbalance > 0)
{
// swaps count is last swap count + total
// number imbalanced brackets
swap += imbalance;
// imbalance decremented by 1 as it solved
// only one imbalance of Left and Right
imbalance--;
}
}
else if (chars[i] == ']')
{
// increment count of Right bracket
countRight++;
// imbalance is reset to current difference
// between Left and Right brackets
imbalance = (countRight - countLeft);
}
}
return swap;
}
// Driver code
public static void Main(string[] args)
{
string s = "[]][][";
Console.WriteLine(swapCount(s));
s = "[[][]]";
Console.WriteLine(swapCount(s));
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript Program to count swaps required
// to balance string
function swapCount(s)
{
let chars = s.split('');
// stores the total number of Left and
// Right brackets encountered
let countLeft = 0, countRight = 0;
// swap stores the number of swaps
// required imbalance maintains the
// number of imbalance pair
let swap = 0, imbalance = 0;
for (let i = 0; i < chars.length; i++)
{
if (chars[i] == '[')
{
// increment count of Left bracket
countLeft++;
if (imbalance > 0)
{
// swaps count is last swap count + total
// number imbalanced brackets
swap += imbalance;
// imbalance decremented by 1 as it solved
// only one imbalance of Left and Right
imbalance--;
}
}
else if (chars[i] == ']')
{
// increment count of Right bracket
countRight++;
// imbalance is reset to current difference
// between Left and Right brackets
imbalance = (countRight - countLeft);
}
}
return swap;
}
let s = "[]][][";
document.write(swapCount(s) + "</br>");
s = "[[][]]";
document.write(swapCount(s));
// This code is contributed by suresh07.
</script>
2 0
Tiempo Complejidad :O(N)
Espacio Auxiliar : O(1)
Este artículo es una contribución de Aarti_Rathi y Aditya Kamath . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuir@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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