Dada una string S de N caracteres que consta de ‘?’ , ‘ 0 ‘ y ‘ 1 ‘ y dos enteros a y b , la tarea es encontrar una string binaria palindrómica con exactamente 0 y b 1 reemplazando el ‘ ? ‘ con ‘ 0 ‘ o ‘ 1 ‘.
Ejemplos:
Entrada: S = “10?????1”, a = 4, b = 4
Salida: 10100101
Explicación: La string de salida es una string binaria palindrómica con exactamente 4 0 y 4 1.Entrada: S = “??????”, a = 5, b = 1
Salida: -1
Explicación: No existe ninguna string palindrómica con exactamente a 0’s yb 1’s.
Enfoque: El problema dado se puede resolver utilizando las siguientes observaciones:
- Para que la string S de N caracteres sea un palíndromo, S[i] = S[Ni-1] debe cumplirse para todos los valores de i en el rango [0, N) .
- Si solo uno de los S[i] y S[Ni-1] es igual a ‘ ? ‘, entonces debe ser reemplazado con el carácter correspondiente del otro índice.
- Si el valor de S[i] y S[Ni-1] es ‘ ? ‘, la opción más óptima es reemplazar ambos con el carácter cuyo recuento requerido es mayor.
Usando las observaciones mencionadas anteriormente, siga los pasos a continuación para resolver el problema:
- Atraviese la string en el rango [0, N/2) , y para los casos en los que solo uno de S[i] y S[N – i – 1] es igual a ‘ ? ‘, reemplácelo con el carácter correspondiente.
- Actualice los valores de a y b restando la cuenta de ‘ 0 ‘ y ‘ 1 ‘ después de la operación anterior. El conteo se puede calcular fácilmente usando la función std::count .
- Ahora recorra la string dada en el rango [0, N/2) , y si ambos S[i] = ‘ ? ‘ y S[Ni-1] = ‘ ? ‘, actualice su valor con el carácter cuyo recuento requerido es más (es decir, con ‘ 0 ‘ si a>b de lo contrario con ‘ 1 ‘).
- En el caso de una longitud de string impar con el carácter central como ‘ ? ‘, actualícelo con carácter con el recuento restante.
- Si el valor de a = 0 y b = 0 , la string almacenada en S es la string requerida. De lo contrario, la string requerida no existe, por lo tanto, devuelva -1 .
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 convert the given string
// to a palindrome with a 0's and b 1's
string convertString(string S, int a, int b)
{
// Stores the size of the string
int N = S.size();
// Loop to iterate over the string
for (int i = 0; i < N / 2; ++i) {
// If one of S[i] or S[N-i-1] is
// equal to '?', replace it with
// corresponding character
if (S[i] == '?'
&& S[N - i - 1] != '?') {
S[i] = S[N - i - 1];
}
else if (S[i] != '?'
&& S[N - i - 1] == '?') {
S[N - i - 1] = S[i];
}
}
// Subtract the count of 0 from the
// required number of zeroes
a = a - count(S.begin(), S.end(), '0');
// Subtract the count of 1 from
// required number of ones
b = b - count(S.begin(), S.end(), '1');
// Traverse the string
for (int i = 0; i < N / 2; ++i) {
// If both S[i] and S[N-i-1] are '?'
if (S[i] == '?' && S[N - i - 1] == '?') {
// If a is greater than b
if (a > b) {
// Update S[i] and S[N-i-1] to '0'
S[i] = S[N - i - 1] = '0';
// Update the value of a
a -= 2;
}
else {
// Update S[i] and S[N-i-1] to '1'
S[i] = S[N - i - 1] = '1';
// Update the value of b
b -= 2;
}
}
}
// Case with middle character '?'
// in case of odd length string
if (S[N / 2] == '?') {
// If a is greater than b
if (a > b) {
// Update middle character
// with '0'
S[N / 2] = '0';
a--;
}
else {
// Update middle character
// by '1'
S[N / 2] = '1';
b--;
}
}
// Return Answer
if (a == 0 && b == 0) {
return S;
}
else {
return "-1";
}
}
// Driver Code
int main()
{
string S = "10?????1";
int a = 4, b = 4;
cout << convertString(S, a, b);
return 0;
}
Java
// Java program for the above approach
class GFG {
// Function to convert the given string
// to a palindrome with a 0's and b 1's
static String convertString(String S, int a, int b)
{
// Stores the size of the string
int N = S.length();
char[] str = S.toCharArray();
// Loop to iterate over the string
for (int i = 0; i < N / 2; ++i) {
// If one of S[i] or S[N-i-1] is
// equal to '?', replace it with
// corresponding character
if (str[i] == '?' && str[N - i - 1] != '?') {
str[i] = str[N - i - 1];
}
else if (str[i] != '?'
&& str[N - i - 1] == '?') {
str[N - i - 1] = str[i];
}
}
// Subtract the count of 0 from the
// required number of zeroes
int countA = 0, countB = 0;
for (int i = 0; i < str.length; i++) {
if (str[i] == '0')
countA++;
else if (str[i] == '1')
countB++;
}
a = a - countA;
// Subtract the count of 1 from
// required number of ones
b = b - countB;
// Traverse the string
for (int i = 0; i < N / 2; ++i) {
// If both S[i] and S[N-i-1] are '?'
if (str[i] == '?' && str[N - i - 1] == '?') {
// If a is greater than b
if (a > b) {
// Update S[i] and S[N-i-1] to '0'
str[i] = '0';
str[N - i - 1] = '0';
// Update the value of a
a -= 2;
}
else {
// Update S[i] and S[N-i-1] to '1'
str[i] = '1';
str[N - i - 1] = '1';
// Update the value of b
b -= 2;
}
}
}
// Case with middle character '?'
// in case of odd length string
if (str[N / 2] == '?') {
// If a is greater than b
if (a > b) {
// Update middle character
// with '0'
str[N / 2] = '0';
a--;
}
else {
// Update middle character
// by '1'
str[N / 2] = '1';
b--;
}
}
// Return Answer
if (a == 0 && b == 0) {
return new String(str);
}
else {
return "-1";
}
}
public static void main(String[] args)
{
String S = "10?????1";
int a = 4, b = 4;
System.out.println(convertString(S, a, b));
}
}
// this code is contributed by phasing17
Python3
# Python program for the above approach
# Function to convert the given string
# to a palindrome with a 0's and b 1's
def convertString(S, a, b):
print(S)
# Stores the size of the string
N = len(S)
# Loop to iterate over the string
for i in range(0, N // 2):
# If one of S[i] or S[N-i-1] is
# equal to '?', replace it with
# corresponding character
if (S[i] == '?' and S[N - i - 1] != '?'):
S[i] = S[N - i - 1]
elif (S[i] != '?' and S[N - i - 1] == '?'):
S[N - i - 1] = S[i]
# Subtract the count of 0 from the
# required number of zeroes
cnt_0 = 0
for i in range(0, N):
if (S[i] == '0'):
cnt_0 += 1
a = a - cnt_0
# Subtract the count of 1 from
# required number of ones
cnt_1 = 0
for i in range(0, N):
if (S[i] == '0'):
cnt_1 += 1
b = b - cnt_1
# Traverse the string
for i in range(0, N // 2):
# If both S[i] and S[N-i-1] are '?'
if (S[i] == '?' and S[N - i - 1] == '?'):
# If a is greater than b
if (a > b):
# Update S[i] and S[N-i-1] to '0'
S[i] = S[N - i - 1] = '0'
# Update the value of a
a -= 2
else:
# Update S[i] and S[N-i-1] to '1'
S[i] = S[N - i - 1] = '1'
# Update the value of b
b -= 2
# Case with middle character '?'
# in case of odd length string
if (S[N // 2] == '?'):
# If a is greater than b
if (a > b):
# Update middle character
# with '0'
S[N // 2] = '0'
a -= 1
else:
# Update middle character
# by '1'
S[N // 2] = '1'
b -= 1
# Return Answer
if (a == 0 and b == 0):
return S
else:
return "-1"
# Driver Code
S = "10?????1"
S = list(S)
a = 4
b = 4
print("".join(convertString(S, a, b)))
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
class GFG {
// Function to convert the given string
// to a palindrome with a 0's and b 1's
static string convertString(string S, int a, int b)
{
// Stores the size of the string
int N = S.Length;
char[] str = S.ToCharArray();
// Loop to iterate over the string
for (int i = 0; i < N / 2; ++i) {
// If one of S[i] or S[N-i-1] is
// equal to '?', replace it with
// corresponding character
if (str[i] == '?' && str[N - i - 1] != '?') {
str[i] = str[N - i - 1];
}
else if (str[i] != '?'
&& str[N - i - 1] == '?') {
str[N - i - 1] = str[i];
}
}
// Subtract the count of 0 from the
// required number of zeroes
int countA = 0, countB = 0;
for (int i = 0; i < str.Length; i++) {
if (str[i] == '0')
countA++;
else if (str[i] == '1')
countB++;
}
a = a - countA;
// Subtract the count of 1 from
// required number of ones
b = b - countB;
// Traverse the string
for (int i = 0; i < N / 2; ++i) {
// If both S[i] and S[N-i-1] are '?'
if (str[i] == '?' && str[N - i - 1] == '?') {
// If a is greater than b
if (a > b) {
// Update S[i] and S[N-i-1] to '0'
str[i] = '0';
str[N - i - 1] = '0';
// Update the value of a
a -= 2;
}
else {
// Update S[i] and S[N-i-1] to '1'
str[i] = '1';
str[N - i - 1] = '1';
// Update the value of b
b -= 2;
}
}
}
// Case with middle character '?'
// in case of odd length string
if (str[N / 2] == '?') {
// If a is greater than b
if (a > b) {
// Update middle character
// with '0'
str[N / 2] = '0';
a--;
}
else {
// Update middle character
// by '1'
str[N / 2] = '1';
b--;
}
}
// Return Answer
if (a == 0 && b == 0) {
return new String(str);
}
else {
return "-1";
}
}
// Driver Code
public static void Main()
{
string S = "10?????1";
int a = 4, b = 4;
Console.Write(convertString(S, a, b));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program for the above approach
// Function to convert the given string
// to a palindrome with a 0's and b 1's
const convertString = (S, a, b) => {
// Stores the size of the string
let N = S.length;
// Loop to iterate over the string
for (let i = 0; i < parseInt(N / 2); ++i) {
// If one of S[i] or S[N-i-1] is
// equal to '?', replace it with
// corresponding character
if (S[i] == '?'
&& S[N - i - 1] != '?') {
S[i] = S[N - i - 1];
}
else if (S[i] != '?'
&& S[N - i - 1] == '?') {
S[N - i - 1] = S[i];
}
}
// Subtract the count of 0 from the
// required number of zeroes
let cnt_0 = 0;
for (let i = 0; i < N; ++i) {
if (S[i] == '0') cnt_0++;
}
a = a - cnt_0;
// Subtract the count of 1 from
// required number of ones
let cnt_1 = 0;
for (let i = 0; i < N; ++i) {
if (S[i] == '0') cnt_1++;
}
b = b - cnt_1;
// Traverse the string
for (let i = 0; i < parseInt(N / 2); ++i) {
// If both S[i] and S[N-i-1] are '?'
if (S[i] == '?' && S[N - i - 1] == '?') {
// If a is greater than b
if (a > b) {
// Update S[i] and S[N-i-1] to '0'
S[i] = S[N - i - 1] = '0';
// Update the value of a
a -= 2;
}
else {
// Update S[i] and S[N-i-1] to '1'
S[i] = S[N - i - 1] = '1';
// Update the value of b
b -= 2;
}
}
}
// Case with middle character '?'
// in case of odd length string
if (S[parseInt(N / 2)] == '?') {
// If a is greater than b
if (a > b) {
// Update middle character
// with '0'
S[parseInt(N / 2)] = '0';
a--;
}
else {
// Update middle character
// by '1'
S[parseInt(N / 2)] = '1';
b--;
}
}
// Return Answer
if (a == 0 && b == 0) {
return S;
}
else {
return "-1";
}
}
// Driver Code
let S = "10?????1";
S = S.split('');
let a = 4, b = 4;
document.write(convertString(S, a, b).join(''));
// This code is contributed by rakeshsahni
</script>
Producción:
10100101
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por anusha00466 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA