Dada una string str que consta de 0, 1 y * , la tarea es encontrar el carácter máximo que aparece entre 0 y 1 después de realizar las operaciones dadas:
- Reemplace * con 0 donde * aparece en el lado izquierdo de los 0 existentes en la string.
- Reemplace * con 1 donde * aparece en el lado derecho de los 1 existentes en la string.
- Si cualquier * se puede reemplazar tanto por 0 como por 1 , entonces permanece sin cambios.
Nota: Si la frecuencia de 0 y 1 es la misma después de realizar las operaciones dadas, imprima -1 .
Ejemplos:
Entrada: str = “**0**1***0”
Salida: 0
Explicación:
Dado que 0 puede reemplazar el * a su izquierda y 1 puede reemplazar el * a su derecha, la string se convierte en 000**1***0Entrada: str = “0*1”
Salida: -1
Explicación:
Tanto 0 como 1 tienen la misma frecuencia, por lo que la salida es -1.
Enfoque: la idea de generar la string resultante final y luego comparar la frecuencia de 0 y 1. A continuación se muestran los pasos:
- Cuente las frecuencias iniciales de 0 y 1 en la string y guárdelas en variables digamos count_0 y count_1 .
- Inicialice una variable, digamos anterior , como -1. Iterar sobre la string y comprobar si el carácter actual es * . Si es así, continúa.
- Si es el primer carácter que se encuentra y es 0 , agregue todo * a count_0 y cambie el anterior al índice actual.
- De lo contrario, si el primer carácter es 1 , cambie anterior al índice actual.
- Si el carácter anterior es 1 y el carácter actual es 0 , agregue la mitad de * entre los caracteres a 0 y la mitad a 1 .
- Si el carácter anterior es 0 y el carácter actual es 1 , entonces no se puede reemplazar ningún carácter * entre ellos.
- Si los caracteres anterior y actual son del mismo tipo, agregue el recuento de * a las frecuencias.
- Compare las frecuencias de 0 y 1 e imprima el carácter máximo que aparece.
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
// maximum occurring character
void solve(string S)
{
// Initialize count of
// zero and one
int count_0 = 0, count_1 = 0;
int prev = -1;
// Iterate over the given string
for (int i = 0; i < S.length(); i++) {
// Count the zeros
if (S[i] == '0')
count_0++;
// Count the ones
else if (S[i] == '1')
count_1++;
}
// Iterate over the given string
for (int i = 0; i < S.length(); i++) {
// Check if character
// is * then continue
if (S[i] == '*')
continue;
// Check if first character
// after * is X
else if (S[i] == '0' && prev == -1) {
// Add all * to
// the frequency of X
count_0 = count_0 + i;
// Set prev to the
// i-th character
prev = i;
}
// Check if first character
// after * is Y
else if (S[i] == '1' && prev == -1) {
// Set prev to the
// i-th character
prev = i;
}
// Check if prev character is 1
// and current character is 0
else if (S[prev] == '1' && S[i] == '0') {
// Half of the * will be
// converted to 0
count_0 = count_0 + (i - prev - 1) / 2;
// Half of the * will be
// converted to 1
count_1 = count_1 + (i - prev - 1) / 2;
prev = i;
}
// Check if prev and current are 1
else if (S[prev] == '1' && S[i] == '1') {
// All * will get converted to 1
count_1 = count_1 + (i - prev - 1);
prev = i;
}
// No * can be replaced
// by either 0 or 1
else if (S[prev] == '0' && S[i] == '1')
// Prev becomes the ith character
prev = i;
// Check if prev and current are 0
else if (S[prev] == '0' && S[i] == '0') {
// All * will get converted to 0
count_0 = count_0 + (i - prev - 1);
prev = i;
}
}
// If frequency of 0
// is more
if (count_0 > count_1)
cout << "0";
// If frequency of 1
// is more
else if (count_1 > count_0)
cout << "1";
else {
cout << -1;
}
}
// Driver code
int main()
{
// Given string
string str = "**0**1***0";
// Function Call
solve(str);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find the
// maximum occurring character
static void solve(String S)
{
// Initialize count of
// zero and one
int count_0 = 0, count_1 = 0;
int prev = -1;
// Iterate over the given string
for(int i = 0; i < S.length(); i++)
{
// Count the zeros
if (S.charAt(i) == '0')
count_0++;
// Count the ones
else if (S.charAt(i) == '1')
count_1++;
}
// Iterate over the given string
for(int i = 0; i < S.length(); i++)
{
// Check if character
// is * then continue
if (S.charAt(i) == '*')
continue;
// Check if first character
// after * is X
else if (S.charAt(i) == '0' && prev == -1)
{
// Add all * to
// the frequency of X
count_0 = count_0 + i;
// Set prev to the
// i-th character
prev = i;
}
// Check if first character
// after * is Y
else if (S.charAt(i) == '1' && prev == -1)
{
// Set prev to the
// i-th character
prev = i;
}
// Check if prev character is 1
// and current character is 0
else if (S.charAt(prev) == '1' &&
S.charAt(i) == '0')
{
// Half of the * will be
// converted to 0
count_0 = count_0 + (i - prev - 1) / 2;
// Half of the * will be
// converted to 1
count_1 = count_1 + (i - prev - 1) / 2;
prev = i;
}
// Check if prev and current are 1
else if (S.charAt(prev) == '1' &&
S.charAt(i) == '1')
{
// All * will get converted to 1
count_1 = count_1 + (i - prev - 1);
prev = i;
}
// No * can be replaced
// by either 0 or 1
else if (S.charAt(prev) == '0' &&
S.charAt(i) == '1')
// Prev becomes the ith character
prev = i;
// Check if prev and current are 0
else if (S.charAt(prev) == '0' &&
S.charAt(i) == '0')
{
// All * will get converted to 0
count_0 = count_0 + (i - prev - 1);
prev = i;
}
}
// If frequency of 0
// is more
if (count_0 > count_1)
System.out.print("0");
// If frequency of 1
// is more
else if (count_1 > count_0)
System.out.print("1");
else
{
System.out.print("-1");
}
}
// Driver code
public static void main (String[] args)
{
// Given string
String str = "**0**1***0";
// Function call
solve(str);
}
}
// This code is contributed by code_hunt
Python3
# Python3 program for the above approach
# Function to find the
# maximum occurring character
def solve(S):
# Initialize count of
# zero and one
count_0 = 0
count_1 = 0
prev = -1
# Iterate over the given string
for i in range(len(S)) :
# Count the zeros
if (S[i] == '0'):
count_0 += 1
# Count the ones
elif (S[i] == '1'):
count_1 += 1
# Iterate over the given string
for i in range(len(S)):
# Check if character
# is * then continue
if (S[i] == '*'):
continue
# Check if first character
# after * is X
elif (S[i] == '0' and prev == -1):
# Add all * to
# the frequency of X
count_0 = count_0 + i
# Set prev to the
# i-th character
prev = i
# Check if first character
# after * is Y
elif (S[i] == '1' and prev == -1):
# Set prev to the
# i-th character
prev = i
# Check if prev character is 1
# and current character is 0
elif (S[prev] == '1' and S[i] == '0'):
# Half of the * will be
# converted to 0
count_0 = count_0 + (i - prev - 1) / 2
# Half of the * will be
# converted to 1
count_1 = count_1 + (i - prev - 1) // 2
prev = i
# Check if prev and current are 1
elif (S[prev] == '1' and S[i] == '1'):
# All * will get converted to 1
count_1 = count_1 + (i - prev - 1)
prev = i
# No * can be replaced
# by either 0 or 1
elif (S[prev] == '0' and S[i] == '1'):
# Prev becomes the ith character
prev = i
# Check if prev and current are 0
elif (S[prev] == '0' and S[i] == '0'):
# All * will get converted to 0
count_0 = count_0 + (i - prev - 1)
prev = i
# If frequency of 0
# is more
if (count_0 > count_1):
print("0")
# If frequency of 1
# is more
elif (count_1 > count_0):
print("1")
else:
print("-1")
# Driver code
# Given string
str = "**0**1***0"
# Function call
solve(str)
# This code is contributed by code_hunt
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the
// maximum occurring character
static void solve(string S)
{
// Initialize count of
// zero and one
int count_0 = 0, count_1 = 0;
int prev = -1;
// Iterate over the given string
for(int i = 0; i < S.Length; i++)
{
// Count the zeros
if (S[i] == '0')
count_0++;
// Count the ones
else if (S[i] == '1')
count_1++;
}
// Iterate over the given string
for(int i = 0; i < S.Length; i++)
{
// Check if character
// is * then continue
if (S[i] == '*')
continue;
// Check if first character
// after * is X
else if (S[i] == '0' && prev == -1)
{
// Add all * to
// the frequency of X
count_0 = count_0 + i;
// Set prev to the
// i-th character
prev = i;
}
// Check if first character
// after * is Y
else if (S[i] == '1' && prev == -1)
{
// Set prev to the
// i-th character
prev = i;
}
// Check if prev character is 1
// and current character is 0
else if (S[prev] == '1' && S[i] == '0')
{
// Half of the * will be
// converted to 0
count_0 = count_0 + (i - prev - 1) / 2;
// Half of the * will be
// converted to 1
count_1 = count_1 + (i - prev - 1) / 2;
prev = i;
}
// Check if prev and current are 1
else if (S[prev] == '1' && S[i] == '1')
{
// All * will get converted to 1
count_1 = count_1 + (i - prev - 1);
prev = i;
}
// No * can be replaced
// by either 0 or 1
else if (S[prev] == '0' && S[i] == '1')
// Prev becomes the ith character
prev = i;
// Check if prev and current are 0
else if (S[prev] == '0' && S[i] == '0')
{
// All * will get converted to 0
count_0 = count_0 + (i - prev - 1);
prev = i;
}
}
// If frequency of 0
// is more
if (count_0 > count_1)
Console.Write("0");
// If frequency of 1
// is more
else if (count_1 > count_0)
Console.Write("1");
else
{
Console.Write("-1");
}
}
// Driver code
public static void Main ()
{
// Given string
string str = "**0**1***0";
// Function call
solve(str);
}
}
// This code is contributed by code_hunt
Javascript
<script>
// javascript program for the above approach
// Function to find the
// maximum occurring character
function solve( S) {
// Initialize count of
// zero and one
var count_0 = 0, count_1 = 0;
var prev = -1;
// Iterate over the given string
for (i = 0; i < S.length; i++) {
// Count the zeros
if (S.charAt(i) == '0')
count_0++;
// Count the ones
else if (S.charAt(i) == '1')
count_1++;
}
// Iterate over the given string
for (i = 0; i < S.length; i++) {
// Check if character
// is * then continue
if (S.charAt(i) == '*')
continue;
// Check if first character
// after * is X
else if (S.charAt(i) == '0' && prev == -1) {
// Add all * to
// the frequency of X
count_0 = count_0 + i;
// Set prev to the
// i-th character
prev = i;
}
// Check if first character
// after * is Y
else if (S.charAt(i) == '1' && prev == -1) {
// Set prev to the
// i-th character
prev = i;
}
// Check if prev character is 1
// and current character is 0
else if (S.charAt(prev) == '1' && S.charAt(i) == '0') {
// Half of the * will be
// converted to 0
count_0 = count_0 + (i - prev - 1) / 2;
// Half of the * will be
// converted to 1
count_1 = count_1 + (i - prev - 1) / 2;
prev = i;
}
// Check if prev and current are 1
else if (S.charAt(prev) == '1' && S.charAt(i) == '1') {
// All * will get converted to 1
count_1 = count_1 + (i - prev - 1);
prev = i;
}
// No * can be replaced
// by either 0 or 1
else if (S.charAt(prev) == '0' && S.charAt(i) == '1')
// Prev becomes the ith character
prev = i;
// Check if prev and current are 0
else if (S.charAt(prev) == '0' && S.charAt(i) == '0') {
// All * will get converted to 0
count_0 = count_0 + (i - prev - 1);
prev = i;
}
}
// If frequency of 0
// is more
if (count_0 > count_1)
document.write("0");
// If frequency of 1
// is more
else if (count_1 > count_0)
document.write("1");
else {
document.write("-1");
}
}
// Driver code
// Given string
var str = "**0**1***0";
// Function call
solve(str);
// This code IS contributed by umadevi9616
</script>
Producción:
0
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por mishrapriyanshu557 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA