Dada una string binaria, la tarea es encontrar el número mínimo de caracteres que se eliminarán de ella para que se vuelva alternativa. Una string binaria es alternativa si no hay dos 0 o 1 consecutivos.
Ejemplos:
Input : s = "000111" Output : 4 We need to delete two 0s and two 1s to make string alternate. Input : s = "0000" Output : 3 We need to delete three characters to make it alternate. Input : s = "11111" Output : 4 Input : s = "01010101" Output : 0 Input : s = "101010" Output : 0
Este problema tiene una solución simple a continuación.
Atravesamos la string de izquierda a derecha y comparamos el carácter actual con el siguiente carácter.
- Si el actual y el siguiente son diferentes, entonces no es necesario realizar la eliminación.
- Si el actual y el siguiente son iguales, debemos realizar una operación de eliminación para que se alternen.
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ program to find minimum number
// of characters to be removed to make
// a string alternate.
#include <bits/stdc++.h>
using namespace std;
// Returns count of minimum characters to
// be removed to make s alternate.
void countToMake0lternate(const string& s)
{
int result = 0;
for (int i = 0; i < (s.length() - 1); i++)
// if two alternating characters
// of string are same
if (s[i] == s[i + 1])
result++; // then need to
// delete a character
return result;
}
// Driver code
int main()
{
cout << countToMake0lternate("000111") << endl;
cout << countToMake0lternate("11111") << endl;
cout << countToMake0lternate("01010101") << endl;
return 0;
}
Java
// Java program to find minimum number
// of characters to be removed to make
// a string alternate.
import java.io.*;
public class GFG {
// Returns count of minimum characters to
// be removed to make s alternate.
static int countToMake0lternate(String s)
{
int result = 0;
for (int i = 0; i < (s.length() - 1); i++)
// if two alternating characters
// of string are same
if (s.charAt(i) == s.charAt(i + 1))
result++; // then need to
// delete a character
return result;
}
// Driver code
static public void main(String[] args)
{
System.out.println(countToMake0lternate("000111"));
System.out.println(countToMake0lternate("11111"));
System.out.println(countToMake0lternate("01010101"));
}
}
// This code is contributed by vt_m.
Python 3
# Python 3 program to find minimum number
# of characters to be removed to make
# a string alternate.
# Returns count of minimum characters
# to be removed to make s alternate.
def countToMake0lternate(s):
result = 0
for i in range(len(s) - 1):
# if two alternating characters
# of string are same
if (s[i] == s[i + 1]):
result += 1 # then need to
# delete a character
return result
# Driver code
if __name__ == "__main__":
print(countToMake0lternate("000111"))
print(countToMake0lternate("11111"))
print(countToMake0lternate("01010101"))
# This code is contributed by ita_c
C#
// C# program to find minimum number
// of characters to be removed to make
// a string alternate.
using System;
public class GFG {
// Returns count of minimum characters to
// be removed to make s alternate.
static int countToMake0lternate(string s)
{
int result = 0;
for (int i = 0; i < (s.Length - 1); i++)
// if two alternating characters
// of string are same
if (s[i] == s[i + 1])
result++; // then need to
// delete a character
return result;
}
// Driver code
static public void Main()
{
Console.WriteLine(countToMake0lternate("000111"));
Console.WriteLine(countToMake0lternate("11111"));
Console.WriteLine(countToMake0lternate("01010101"));
}
}
// This article is contributed by vt_m.
PHP
<?php
// PHP program to find minimum number
// of characters to be removed to make
// a string alternate.
// Returns count of minimum characters
// to be removed to make s alternate.
function countToMake0lternate($s)
{
$result = 0;
for ($i = 0; $i < (strlen($s) - 1); $i++)
// if two alternating characters
// of string are same
if ($s[$i] == $s[$i + 1])
// then need to
// delete a character
$result++;
return $result;
}
// Driver code
echo countToMake0lternate("000111"),"\n" ;
echo countToMake0lternate("11111"),"\n" ;
echo countToMake0lternate("01010101") ;
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// Javascript program to find minimum number
// of characters to be removed to make
// a string alternate.
// Returns count of minimum characters to
// be removed to make s alternate.
function countToMake0lternate(s)
{
let result = 0;
for (let i = 0; i < (s.length - 1); i++)
// if two alternating characters
// of string are same
if (s[i] == s[i+1])
result++; // then need to
// delete a character
return result;
}
// Driver code
document.write(countToMake0lternate("000111")+"<br>");
document.write(countToMake0lternate("11111")+"<br>");
document.write(countToMake0lternate("01010101")+"<br>");
// This code is contributed by rag2127
</script>
Producción:
4 4 0
Complejidad de tiempo: O (n) donde n es el número de caracteres en la string de entrada.
Espacio auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi y Ravi Maurya(Trojan) . 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 review-team@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