Dada una string binaria S de 0s y 1s . La tarea es convertir la string dada en una secuencia de caracteres alternativos mediante las siguientes operaciones:
- Elimine algunos prefijos del principio y agréguelos al final.
- Voltee algunos o todos los bits en la string dada.
Imprime el número mínimo de bits que se invertirán para que la string dada se alterné.
Ejemplos:
Entrada: S = «001»
Salida: 0
Explicación:
No es necesario voltear ningún elemento, podemos obtener una secuencia alterna usando la rotación a la izquierda: 010.Entrada: S = “000001100”
Salida: 3
Explicación:
Siga los pasos para encontrar los giros mínimos para obtener una secuencia alterna:
1. Después de rotar la secuencia 6 veces hacia la izquierda, obtendremos: 100000001
2. Ahora podemos aplicar la operación de volteo de la siguiente manera: 101000001 – > 101010001 -> 101010101
Por lo tanto, los giros mínimos para alternar strings son 3.
Enfoque ingenuo: El enfoque ingenuo consiste en tomar todas las N combinaciones posibles y calcular el número mínimo de bits para invertir en cada una de esas strings. Imprime el recuento mínimo entre todas esas combinaciones.
Complejidad de tiempo: O(N 2 ), donde N es la longitud de la string.
Espacio Auxiliar: O(N)
Enfoque eficiente: esto se puede resolver observando que la string final será del tipo «101010…» o «010101…» , de modo que todos los 1 estarán en posiciones pares o impares. Siga los pasos a continuación para resolver el problema:
- Cree una array de suma de prefijos donde pref[i] significa una cantidad de cambios necesarios hasta el índice i.
- Cree arrays de prefijos para los dos patrones anteriores.
- Verifique para cada i , si la substring [0, i] se agrega al final, cuántos caracteres se requieren voltear.
- Imprima el número mínimo de vueltas entre todas las substrings en los pasos anteriores.
¿Por qué solo las strings de longitud impar se consideran para la rotación y por qué la rotación no tendrá efecto en la string de longitud par?
Intentaré explicar esto con el siguiente ejemplo,
Suponga que tiene la secuencia 011000 que tiene una longitud uniforme. Sin rotación, puede cambiarlo a 010101 o 101010. Ahora suponga que elige agregar 01 al final. La secuencia se convierte en 100001, que se puede cambiar a 010101 o 101010. Si compara cada carácter, verá que es el mismo caso que sin rotación. 1000 corresponde a 0101 o 1010 en ambos casos y 01 a 01 o 10.
Pero ahora considere un caso de longitud impar, 01100. Sin rotación, puede cambiarlo a 01010 o 10101. Ahora suponga que elige agregar 01 al final. La secuencia se convierte en 10001, que se puede cambiar a 01010 o 10101. Ahora, si compara cada carácter, verá que 100 corresponde a 010 o 101 en ambos casos, pero 01 corresponde a 01 cuando 100 es 010 en caso de que no haya rotación y 101 en caso de rotación.
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 that finds the minimum
// number of flips to make the
// binary string alternating if
// left circular rotation is allowed
int MinimumFlips(string s, int n)
{
int a[n];
for(int i = 0; i < n; i++)
{
a[i] = (s[i] == '1' ? 1 : 0);
}
// Initialize prefix arrays to store
// number of changes required to put
// 1s at either even or odd position
int oddone[n + 1];
int evenone[n + 1];
oddone[0] = 0;
evenone[0] = 0;
for(int i = 0; i < n; i++)
{
// If i is odd
if (i % 2 != 0)
{
// Update the oddone
// and evenone count
oddone[i + 1] = oddone[i] +
(a[i] == 1 ? 1 : 0);
evenone[i + 1] = evenone[i] +
(a[i] == 0 ? 1 : 0);
}
// Else i is even
else
{
// Update the oddone
// and evenone count
oddone[i + 1] = oddone[i] +
(a[i] == 0 ? 1 : 0);
evenone[i + 1] = evenone[i] +
(a[i] == 1 ? 1 : 0);
}
}
// Initialize minimum flips
int minimum = min(oddone[n], evenone[n]);
// Check if substring[0, i] is
// appended at end how many
// changes will be required
for(int i = 0; i < n; i++)
{
if (n % 2 != 0)
{
minimum = min(minimum,
oddone[n] -
oddone[i + 1] +
evenone[i + 1]);
minimum = min(minimum,
evenone[n] -
evenone[i + 1] +
oddone[i + 1]);
}
}
// Return minimum flips
return minimum;
}
// Driver Code
int main()
{
// Given String
string S = "000001100";
// Length of given string
int n = S.length();
// Function call
cout << (MinimumFlips(S, n));
}
// This code is contributed by chitranayal
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function that finds the minimum
// number of flips to make the
// binary string alternating if
// left circular rotation is allowed
static int MinimumFlips(String s, int n)
{
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = (s.charAt(i) == '1' ? 1 : 0);
}
// Initialize prefix arrays to store
// number of changes required to put
// 1s at either even or odd position
int[] oddone = new int[n + 1];
int[] evenone = new int[n + 1];
oddone[0] = 0;
evenone[0] = 0;
for (int i = 0; i < n; i++) {
// If i is odd
if (i % 2 != 0) {
// Update the oddone
// and evenone count
oddone[i + 1]
= oddone[i]
+ (a[i] == 1 ? 1 : 0);
evenone[i + 1]
= evenone[i]
+ (a[i] == 0 ? 1 : 0);
}
// Else i is even
else {
// Update the oddone
// and evenone count
oddone[i + 1]
= oddone[i]
+ (a[i] == 0 ? 1 : 0);
evenone[i + 1]
= evenone[i]
+ (a[i] == 1 ? 1 : 0);
}
}
// Initialize minimum flips
int minimum = Math.min(oddone[n],
evenone[n]);
// Check if substring[0, i] is
// appended at end how many
// changes will be required
for (int i = 0; i < n; i++) {
if (n % 2 != 0) {
minimum = Math.min(minimum,
oddone[n]
- oddone[i + 1]
+ evenone[i + 1]);
minimum = Math.min(minimum,
evenone[n]
- evenone[i + 1]
+ oddone[i + 1]);
}
}
// Return minimum flips
return minimum;
}
// Driver Code
public static void main(String[] args)
{
// Given String
String S = "000001100";
// Length of given string
int n = S.length();
// Function call
System.out.print(MinimumFlips(S, n));
}
}
Python3
# Python3 program for the above approach # Function that finds the minimum # number of flips to make the # binary string alternating if # left circular rotation is allowed def MinimumFlips(s, n): a = [0] * n for i in range(n): a[i] = 1 if s[i] == '1' else 0 # Initialize prefix arrays to store # number of changes required to put # 1s at either even or odd position oddone = [0] * (n + 1) evenone = [0] * (n + 1) for i in range(n): # If i is odd if(i % 2 != 0): # Update the oddone # and evenone count if(a[i] == 1): oddone[i + 1] = oddone[i] + 1 else: oddone[i + 1] = oddone[i] + 0 if(a[i] == 0): evenone[i + 1] = evenone[i] + 1 else: evenone[i + 1] = evenone[i] + 0 # Else i is even else: # Update the oddone # and evenone count if (a[i] == 0): oddone[i + 1] = oddone[i] + 1 else: oddone[i + 1] = oddone[i] + 0 if (a[i] == 1): evenone[i + 1] = evenone[i] + 1 else: evenone[i + 1] = evenone[i] + 0 # Initialize minimum flips minimum = min(oddone[n], evenone[n]) # Check if substring[0, i] is # appended at end how many # changes will be required for i in range(n): if(n % 2 != 0): minimum = min(minimum, oddone[n] - oddone[i + 1] + evenone[i + 1]) minimum = min(minimum, evenone[n] - evenone[i + 1] + oddone[i + 1]) # Return minimum flips return minimum # Driver Code # Given String S = "000001100" # Length of given string n = len(S) # Function call print(MinimumFlips(S, n)) # This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
class GFG{
// Function that finds the minimum
// number of flips to make the
// binary string alternating if
// left circular rotation is allowed
static int MinimumFlips(String s, int n)
{
int[] a = new int[n];
for (int i = 0; i < n; i++)
{
a[i] = (s[i] == '1' ? 1 : 0);
}
// Initialize prefix arrays to store
// number of changes required to put
// 1s at either even or odd position
int[] oddone = new int[n + 1];
int[] evenone = new int[n + 1];
oddone[0] = 0;
evenone[0] = 0;
for (int i = 0; i < n; i++)
{
// If i is odd
if (i % 2 != 0)
{
// Update the oddone
// and evenone count
oddone[i + 1] = oddone[i] +
(a[i] == 1 ? 1 : 0);
evenone[i + 1] = evenone[i] +
(a[i] == 0 ? 1 : 0);
}
// Else i is even
else
{
// Update the oddone
// and evenone count
oddone[i + 1] = oddone[i] +
(a[i] == 0 ? 1 : 0);
evenone[i + 1] = evenone[i] +
(a[i] == 1 ? 1 : 0);
}
}
// Initialize minimum flips
int minimum = Math.Min(oddone[n],
evenone[n]);
// Check if substring[0, i] is
// appended at end how many
// changes will be required
for (int i = 0; i < n; i++)
{
if (n % 2 != 0)
{
minimum = Math.Min(minimum, oddone[n] -
oddone[i + 1] +
evenone[i + 1]);
minimum = Math.Min(minimum, evenone[n] -
evenone[i + 1] +
oddone[i + 1]);
}
}
// Return minimum flips
return minimum;
}
// Driver Code
public static void Main(String[] args)
{
// Given String
String S = "000001100";
// Length of given string
int n = S.Length;
// Function call
Console.Write(MinimumFlips(S, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program for the
// above approach
// Function that finds the minimum
// number of flips to make the
// binary string alternating if
// left circular rotation is allowed
function MinimumFlips(s, n)
{
let a = Array.from({length: n+1}, (_, i) => 0);
for (let i = 0; i < n; i++) {
a[i] = (s[i] == '1' ? 1 : 0);
}
// Initialize prefix arrays to store
// number of changes required to put
// 1s at either even or odd position
let oddone = Array.from({length: n+1}, (_, i) => 0);
let evenone = Array.from({length: n+1}, (_, i) => 0);
oddone[0] = 0;
evenone[0] = 0;
for (let i = 0; i < n; i++) {
// If i is odd
if (i % 2 != 0) {
// Update the oddone
// and evenone count
oddone[i + 1]
= oddone[i]
+ (a[i] == 1 ? 1 : 0);
evenone[i + 1]
= evenone[i]
+ (a[i] == 0 ? 1 : 0);
}
// Else i is even
else {
// Update the oddone
// and evenone count
oddone[i + 1]
= oddone[i]
+ (a[i] == 0 ? 1 : 0);
evenone[i + 1]
= evenone[i]
+ (a[i] == 1 ? 1 : 0);
}
}
// Initialize minimum flips
let minimum = Math.min(oddone[n],
evenone[n]);
// Check if substring[0, i] is
// appended at end how many
// changes will be required
for (let i = 0; i < n; i++) {
if (n % 2 != 0) {
minimum = Math.min(minimum,
oddone[n]
- oddone[i + 1]
+ evenone[i + 1]);
minimum = Math.min(minimum,
evenone[n]
- evenone[i + 1]
+ oddone[i + 1]);
}
}
// Return minimum flips
return minimum;
}
// Driver Code
// Given String
let S = "000001100";
// Length of given string
let n = S.length;
// Function call
document.write(MinimumFlips(S, n));
</script>
3
Complejidad de tiempo: O(N), donde N es la longitud de la string dada.
Espacio Auxiliar: O(N)