Dada una string binaria S de tamaño N (donde N es par), la tarea es encontrar el costo mínimo de equilibrar la string binaria dada cambiando uno de los diferentes caracteres adyacentes al costo de 1 unidad o intercambiando los caracteres en los índices i y j tales que (i < j) a costa de (j – i) unidad . Si es imposible equilibrar la string, se imprime “-1” .
Una string binaria está equilibrada si se puede reducir a una string vacía eliminando dos caracteres alternos consecutivos a la vez y luego concatenando los caracteres restantes.
Ejemplos:
Entrada: S = “110110”
Salida: 1
Explicación: Se realizan las siguientes operaciones:
Operación 1: Como los caracteres adyacentes en los índices 0 y 1 son diferentes, cambiar S[0] modifica S a “010110”. Costo = 1 .Después de completar las operaciones anteriores, la string dada se equilibra, ya que se puede reducir a una string vacía eliminando dos caracteres alternos consecutivos.
Por lo tanto, el costo total es 1.Entrada: S = “11100”
Salida: -1
Enfoque: El problema dado se puede resolver en base a las observaciones de que el cambio de los diferentes caracteres adyacentes es más óptimo que el uso del intercambio de caracteres y la posición de los 0 y los 1 en la string no importa. Siga los pasos a continuación para resolver el problema:
- Si todos los caracteres son iguales , es imposible equilibrar la string. Por lo tanto, imprima “-1” .
- Almacene el recuento de 1 y 0 en variables, digamos count1 y count0 respectivamente.
- Almacene la diferencia absoluta de count1 y count0 en una variable K .
- Ahora, invierta los caracteres K/2 para equilibrar la string e imprima el valor de K/2 como resultado.
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 find the minimum cost
// to convert the given string into
// balanced string
void findMinimumCost(string s, int N)
{
// Stores count of 1's and 0's in
// the string
int count_1 = 0, count_0 = 0;
// Traverse the string
for (int i = 0; i < N; i++) {
if (s[i] == '1')
// Increment count1
count_1++;
else
// Increment count 0
count_0++;
}
// Stores absolute difference of
// counts of 0's and 1's
int k = abs(count_0 - count_1);
// If string consists of only
// 0's and 1's
if (count_1 == N || count_0 == N)
cout << -1 << endl;
// Print minimum cost
else
cout << k / 2 << endl;
}
// Driver Code
int main()
{
string S = "110110";
int N = S.length();
findMinimumCost(S, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to find the minimum cost
// to convert the given string into
// balanced string
static void findMinimumCost(String s, int N)
{
// Stores count of 1's and 0's in
// the string
int count_1 = 0, count_0 = 0;
// Traverse the string
for (int i = 0; i < N; i++) {
if (s.charAt(i) == '1')
// Increment count1
count_1++;
else
// Increment count 0
count_0++;
}
// Stores absolute difference of
// counts of 0's and 1's
int k = Math.abs(count_0 - count_1);
// If string consists of only
// 0's and 1's
if (count_1 == N || count_0 == N)
System.out.println( -1);
// Print minimum cost
else
System.out.println( k / 2);
}
// Driver Code
public static void main(String[] args)
{
String S = "110110";
int N = S.length();
findMinimumCost(S, N);
}
}
// This code is contributed by code_hunt.
Python3
# Python3 program for the above approach # Function to find the minimum cost # to convert the given into # balanced string def findMinimumCost(s, N): # Stores count of 1's and 0's in # the string count_1, count_0 = 0, 0 # Traverse the string for i in range(N): if (s[i] == '1'): # Increment count1 count_1 += 1 else: # Increment count 0 count_0 += 1 # Stores absolute difference of # counts of 0's and 1's k = abs(count_0 - count_1) # If consists of only # 0's and 1's if (count_1 == N or count_0 == N): print(-1) # Print the minimum cost else: print(k // 2) # Driver Code if __name__ == '__main__': S = "110110" N = len(S) findMinimumCost(S, N) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum cost
// to convert the given string into
// balanced string
static void findMinimumCost(String s, int N)
{
// Stores count of 1's and 0's in
// the string
int count_1 = 0, count_0 = 0;
// Traverse the string
for(int i = 0; i < N; i++)
{
if (s[i] == '1')
// Increment count1
count_1++;
else
// Increment count 0
count_0++;
}
// Stores absolute difference of
// counts of 0's and 1's
int k = Math.Abs(count_0 - count_1);
// If string consists of only
// 0's and 1's
if (count_1 == N || count_0 == N)
Console.WriteLine(-1);
// Print minimum cost
else
Console.WriteLine(k / 2);
}
// Driver Code
static public void Main()
{
String S = "110110";
int N = S.Length;
findMinimumCost(S, N);
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the minimum cost
// to convert the given string into
// balanced string
function findMinimumCost(s, N)
{
// Stores count of 1's and 0's in
// the string
let count_1 = 0, count_0 = 0;
// Traverse the string
for (let i = 0; i < N; i++) {
if (s[i] == '1')
// Increment count1
count_1++;
else
// Increment count 0
count_0++;
}
// Stores absolute difference of
// counts of 0's and 1's
let k = Math.abs(count_0 - count_1);
// If string consists of only
// 0's and 1's
if (count_1 == N || count_0 == N)
document.write( -1);
// Print minimum cost
else
document.write( k / 2);
}
// Driver Code
let S = "110110";
let N = S.length;
findMinimumCost(S, N);
</script>
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aniket173000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA