Dada una string binaria S que consta de N caracteres, la tarea es encontrar el número mínimo de vueltas necesarias para que no existan tres mismos caracteres consecutivos.
Ejemplos:
Entrada: S = “1100011”
Salida: 1
Explicación:
Voltear el carácter en el índice 3 modifica la string S “1101011” que no tiene tres caracteres iguales consecutivos. Por lo tanto, el número mínimo de lanzamientos necesarios es 1.Entrada: S = “0001111101”
Salida: 2
Enfoque: el problema dado se puede resolver considerando cada tres caracteres consecutivos y, si son iguales, entonces aumente la cantidad de volteos requeridos, ya que se necesita voltear uno de los tres caracteres. Siga los pasos a continuación para resolver el problema:
- Inicialice la variable, digamos contar como 0 que almacena la cantidad mínima de vueltas requeridas.
- Si el tamaño de la string es menor que igual a 2, devuelve 0 ya que no hay necesidad de voltear.
- Iterar sobre el rango [0, N – 2) usando la variable i y realizar los siguientes pasos:
- Si el carácter en los índices i , (i + 1) y (i + 2) son los mismos, aumente el valor de count en 1 y el valor de i en 3 .
- De lo contrario, incrementa el valor de i en 1 .
- Después de realizar los pasos anteriores, imprima el valor de conteo 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 number
// of flips to make all three pairs of
// consecutive characters different
int minFlips(string str)
{
// Stores resultant count of pairs
int count = 0;
// Base Case
if (str.size() <= 2) {
return 0;
}
// Iterate over the range [0, N - 2]
for (int i = 0; i < str.size() - 2;) {
// If the consecutive 3 numbers
// are the same then increment
// the count and the counter
if (str[i] == str[i + 1]
&& str[i + 2] == str[i + 1]) {
i = i + 3;
count++;
}
else {
i++;
}
}
// Return the answer
return count;
}
// Driver Code
int main()
{
string S = "0011101";
cout << minFlips(S);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Function to find the minimum number
// of flips to make all three pairs of
// consecutive characters different
static int minFlips(String str)
{
// Stores resultant count of pairs
int count = 0;
// Base Case
if (str.length() <= 2) {
return 0;
}
// Iterate over the range [0, N - 2]
for (int i = 0; i < str.length() - 2😉 {
// If the consecutive 3 numbers
// are the same then increment
// the count and the counter
if (str.charAt(i) == str.charAt(i+1)
&& str.charAt(i+2) == str.charAt(i+1)) {
i = i + 3;
count++;
}
else {
i++;
}
}
// Return the answer
return count;
}
// Driver Code
public static void main(String[] args)
{
String S = "0011101";
System.out.println(minFlips(S));
}
}
// This code is contributed by dwivediyash
Python3
# python 3 program for the above approach # # Function to find the minimum number # of flips to make all three pairs of # consecutive characters different def minFlips(st): # Stores resultant count of pairs count = 0 # Base Case if (len(st) <= 2): return 0 # Iterate over the range [0, N - 2] for i in range(len(st) - 2): # If the consecutive 3 numbers # are the same then increment # the count and the counter if (st[i] == st[i + 1] and st[i + 2] == st[i + 1]): i = i + 3 count += 1 else: i += 1 # Return the answer return count # Driver Code if __name__ == "__main__": S = "0011101" print(minFlips(S)) # This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the minimum number
// of flips to make all three pairs of
// consecutive characters different
function minFlips(str) {
// Stores resultant count of pairs
let count = 0;
// Base Case
if (str.length <= 2) {
return 0;
}
// Iterate over the range [0, N - 2]
for (let i = 0; i < str.length - 2;) {
// If the consecutive 3 numbers
// are the same then increment
// the count and the counter
if (str[i] == str[i + 1]
&& str[i + 2] == str[i + 1]) {
i = i + 3;
count++;
}
else {
i++;
}
}
// Return the answer
return count;
}
// Driver Code
let S = "0011101";
document.write(minFlips(S));
// This code is contributed by Potta Lokesh
</script>
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to find the minimum number
// of flips to make all three pairs of
// consecutive characters different
static int minFlips(string str)
{
// Stores resultant count of pairs
int count = 0;
// Base Case
if (str.Length <= 2) {
return 0;
}
// Iterate over the range [0, N - 2]
for (int i = 0; i < str.Length - 2;) {
// If the consecutive 3 numbers
// are the same then increment
// the count and the counter
if (str[i] == str[i+1]
&& str[i+2] == str[i+1]) {
i = i + 3;
count++;
}
else {
i++;
}
}
// Return the answer
return count;
}
// Driver Code
public static void Main(string[] args)
{
string S = "0011101";
Console.WriteLine(minFlips(S));
}
}
// This code is contributed by AnkThon
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)