Dada una string S de longitud N que consta de «?» y minúsculas, la tarea es reemplazar «?» con letras minúsculas de modo que ningún carácter adyacente sea el mismo. Si existe más de una combinación posible, imprima cualquiera de ellas.
Ejemplos:
Entrada: S = “?a?a”
Salida: baba
Explicación:
Reemplazar todos los ‘?’ con ‘b’ modifica la string a “baba”.
Dado que ningún carácter adyacente en «baba» es el mismo, imprima la string como respuesta.Entrada: S = “???”
Salida: aca
Explicación:
Reemplazar primero ‘?’ con un’.
Reemplace el segundo ‘?’ con ‘c’.
Reemplazar el tercer ‘?’ con un’. Ahora, la string modificada es «aca».
Por lo tanto, no hay caracteres adyacentes en “ca” que sean iguales.
Enfoque ingenuo: el enfoque más simple es intentar generar todas las permutaciones posibles de la string dada que consta de letras minúsculas. Puede haber 26 strings N. En cada una de estas strings, verifique si los caracteres adyacentes coinciden o no y si todos los caracteres en minúscula en la string dada coinciden con la permutación elegida de la string.
Complejidad de tiempo: O(N*26 N ), donde N es la longitud de la string dada.
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es reemplazar cada ‘?’ por el carácter ‘a’ y verifique si este carácter es igual al carácter adyacente o no. Si es igual al carácter adyacente, incremente el carácter actual. A continuación se muestran los pasos:
- Si el primer carácter de la string es ‘?’ luego reemplácelo con ‘a’ y si es igual al siguiente carácter, incremente el carácter actual en 1
- Recorra la string dada usando una variable i sobre el rango [1, N – 1] y si el carácter actual es ‘?’ y haz lo siguiente:
- Actualice el carácter en el índice i como s[i] = ‘a’ .
- Ahora, si el carácter en el índice i y (i – 1) son iguales, incremente el carácter actual en 1 .
- Ahora, si el carácter en el índice i y (i + 1) son iguales, incremente el carácter actual en 1 .
- Ahora, si el carácter en el índice i y (i – 1) son los mismos nuevamente, incremente el carácter actual en 1 . Este paso es obligatorio porque después de incrementar el carácter en el paso anterior, es posible que el carácter en el índice i y (i – 1) sean iguales.
- Si el último carácter de la string es ‘?’ luego reemplácelo con ‘a’ y si es igual al carácter anterior, incremente el último carácter en 1
- Imprima la string después de los pasos anteriores.
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 replace all '?' with
// lowercase alphabets such that each
// adjacent character is different
string changeString(string S)
{
// Store the given string
string s = S;
int N = (int)s.length();
// If the first character is '?'
if (s[0] == '?') {
s[0] = 'a';
if (s[0] == s[1]) {
s[0]++;
}
}
// Traverse the string [1, N - 1]
for (int i = 1; i < N - 1; i++) {
// If the current character is '?'
if (s[i] == '?') {
// Change the character
s[i] = 'a';
// Check equality with
// the previous character
if (s[i] == s[i - 1]) {
s[i]++;
}
// Check equality with
// the next character
if (s[i] == s[i + 1]) {
s[i]++;
}
// Check equality with
// the previous character
if (s[i] == s[i - 1]) {
s[i]++;
}
}
}
// If the last character is '?'
if (s[N - 1] == '?') {
// Change character
s[N - 1] = 'a';
// Check with previous character
if (s[N - 1] == s[N - 2]) {
s[N - 1]++;
}
}
// Return the resultant string
return s;
}
// Driver Code
int main()
{
// Given string S
string S = "?a?a";
// Function Call
cout << changeString(S);
return 0;
}
Java
// Java program for
// the above approach
class GFG{
// Function that replace all '?' with
// lowercase alphabets such that each
// adjacent character is different
static String changeString(String S)
{
// Store the given String
char []s = S.toCharArray();
int N = (int)S.length();
// If the first character is '?'
if (s[0] == '?')
{
s[0] = 'a';
if (s[0] == s[1])
{
s[0]++;
}
}
// Traverse the String [1, N - 1]
for (int i = 1; i < N - 1; i++)
{
// If the current
// character is '?'
if (s[i] == '?')
{
// Change the character
s[i] = 'a';
// Check equality with
// the previous character
if (s[i] == s[i - 1])
{
s[i]++;
}
// Check equality with
// the next character
if (s[i] == s[i + 1])
{
s[i]++;
}
// Check equality with
// the previous character
if (s[i] == s[i - 1])
{
s[i]++;
}
}
}
// If the last character is '?'
if (s[N - 1] == '?')
{
// Change character
s[N - 1] = 'a';
// Check with previous
// character
if (s[N - 1] == s[N - 2])
{
s[N - 1]++;
}
}
String ans = "";
for(int i = 0; i < s.length; i++)
{
ans += s[i];
}
// Return the resultant String
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given String S
String S = "?a?a";
// Function Call
System.out.print(changeString(S));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for # the above approach # Function that replace all '?' with # lowercase alphabets such that each # adjacent character is different def changeString(S): # Store the given String N = len(S) s = [' '] * (len(S)) for i in range(len(S)): s[i] = S[i] # If the first character is '?' if (s[0] == '?'): s[0] = 'a' if (s[0] == s[1]): s[0] = chr(ord(s[0]) + 1) # Traverse the String [1, N - 1] for i in range(1, N - 1): # If the current # character is '?' if (s[i] == '?'): # Change the character s[i] = 'a' # Check equality with # the previous character if (s[i] == s[i - 1]): s[i] = chr(ord(s[i]) + 1) # Check equality with # the next character if (s[i] == s[i + 1]): s[i] = chr(ord(s[i]) + 1) # Check equality with # the previous character if (s[i] == s[i - 1]): s[i] = chr(ord(s[i]) + 1) # If the last character is '?' if (s[N - 1] == '?'): # Change character s[N - 1] = 'a' # Check with previous # character if (s[N - 1] == s[N - 2]): s[N - 1] += 1 ans = "" for i in range(len(s)): ans += s[i] # Return the resultant String return ans # Driver Code if __name__ == '__main__': # Given String S S = "?a?a" # Function Call print(changeString(S)) # This code is contributed by gauravrajput1
C#
// C# program for the above approach
using System;
class GFG{
// Function that replace all '?' with
// lowercase alphabets such that each
// adjacent character is different
static string changeString(string S)
{
// Store the given String
char []s = S.ToCharArray();
int N = S.Length;
// If the first character is '?'
if (s[0] == '?')
{
s[0] = 'a';
if (s[0] == s[1])
{
s[0]++;
}
}
// Traverse the String [1, N - 1]
for(int i = 1; i < N - 1; i++)
{
// If the current
// character is '?'
if (s[i] == '?')
{
// Change the character
s[i] = 'a';
// Check equality with
// the previous character
if (s[i] == s[i - 1])
{
s[i]++;
}
// Check equality with
// the next character
if (s[i] == s[i + 1])
{
s[i]++;
}
// Check equality with
// the previous character
if (s[i] == s[i - 1])
{
s[i]++;
}
}
}
// If the last character is '?'
if (s[N - 1] == '?')
{
// Change character
s[N - 1] = 'a';
// Check with previous
// character
if (s[N - 1] == s[N - 2])
{
s[N - 1]++;
}
}
string ans = "";
for(int i = 0; i < s.Length; i++)
{
ans += s[i];
}
// Return the resultant String
return ans;
}
// Driver Code
public static void Main()
{
// Given String S
string S = "?a?a";
// Function Call
Console.WriteLine(changeString(S));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for
// the above approach
// Function that replace all '?' with
// lowercase alphabets such that each
// adjacent character is different
function changeString(S)
{
// Store the given String
let s = S.split("");
let N = S.length;
// If the first character is '?'
if (s[0] == '?')
{
s[0] = 'a';
if (s[0] == s[1])
{
s[0] = String.fromCharCode(s[0].charCodeAt(0)+1);
}
}
// Traverse the String [1, N - 1]
for (let i = 1; i < N - 1; i++)
{
// If the current
// character is '?'
if (s[i] == '?')
{
// Change the character
s[i] = 'a';
// Check equality with
// the previous character
if (s[i] == s[i - 1])
{
s[i] = String.fromCharCode(s[i].charCodeAt(0)+1);
}
// Check equality with
// the next character
if (s[i] == s[i + 1])
{
s[i] = String.fromCharCode(s[i].charCodeAt(0)+1);
}
// Check equality with
// the previous character
if (s[i] == s[i - 1])
{
s[i]=String.fromCharCode(s[i].charCodeAt(0)+1);
}
}
}
// If the last character is '?'
if (s[N - 1] == '?')
{
// Change character
s[N - 1] = 'a';
// Check with previous
// character
if (s[N - 1] == s[N - 2])
{
s[N - 1]++;
}
}
let ans = "";
for(let i = 0; i < s.length; i++)
{
ans += s[i];
}
// Return the resultant String
return ans;
}
// Driver Code
// Given String S
let S = "?a?a";
// Function Call
document.write(changeString(S));
// This code is contributed by patel2127
</script>
Producción
baba
Complejidad de tiempo: O(N), donde N es la longitud de la string dada.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA