Dada una string str , algunos de cuyos caracteres faltan y están representados por un ‘*’ . La tarea es sustituir los caracteres que faltan para hacer el palíndromo lexicográficamente más pequeño. Si no es posible hacer el palíndromo de strings, imprima -1 .
Ejemplos:
Entrada: str = “ab*a”
Salida: abba
Entrada: a*b
Salida: -1
No podemos convertirlo en palíndromo, por lo que la salida es -1.
Acercarse:
- Coloque el marcador ‘i’ al principio de la string y el marcador ‘j’ al final de la string.
- Si faltan caracteres en ambas posiciones, sustituya ambos caracteres con ‘a’ para que sea el palíndromo lexicográficamente más pequeño.
- Si falta el carácter en la posición i -ésima o j -ésima , reemplácelo con el carácter j -ésimo o i -ésimo respectivamente.
- Si el carácter en las posiciones i -ésima y j -ésima no son iguales , entonces la string no puede convertirse en un palíndromo e imprimir -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the lexicographically
// smallest palindrome that can be made from
// the given string after replacing
// the required characters
string makePalindrome(string str)
{
int i = 0, j = str.length() - 1;
while (i <= j) {
// If characters are missing at both the positions
// then substitute it with 'a'
if (str[i] == '*' && str[j] == '*') {
str[i] = 'a';
str[j] = 'a';
}
// If only str[j] = '*' then update it
// with the value at str[i]
else if (str[j] == '*')
str[j] = str[i];
// If only str[i] = '*' then update it
// with the value at str[j]
else if (str[i] == '*')
str[i] = str[j];
// If characters at both positions
// are not equal and != '*' then the string
// cannot be made palindrome
else if (str[i] != str[j])
return "-1";
i++;
j--;
}
// Return the required palindrome
return str;
}
// Driver code
int main()
{
string str = "na*an";
cout << makePalindrome(str);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the lexicographically
// smallest palindrome that can be made from
// the given string after replacing
// the required characters
static String makePalindrome(char[] str)
{
int i = 0, j = str.length - 1;
while (i <= j)
{
// If characters are missing at both the positions
// then substitute it with 'a'
if (str[i] == '*' && str[j] == '*')
{
str[i] = 'a';
str[j] = 'a';
}
// If only str[j] = '*' then update it
// with the value at str[i]
else if (str[j] == '*')
str[j] = str[i];
// If only str[i] = '*' then update it
// with the value at str[j]
else if (str[i] == '*')
str[i] = str[j];
// If characters at both positions
// are not equal and != '*' then the string
// cannot be made palindrome
else if (str[i] != str[j])
return "-1";
i++;
j--;
}
// Return the required palindrome
return String.valueOf(str);
}
// Driver code
public static void main(String[] args)
{
char[] str = "na*an".toCharArray();
System.out.println(makePalindrome(str));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 implementation of the approach # Function to return the lexicographically # smallest palindrome that can be made from # the given string after replacing # the required characters def makePalindrome(str1): i = 0 j = len(str1) - 1 str1 = list(str1) while (i <= j): # If characters are missing # at both the positions # then substitute it with 'a' if (str1[i] == '*' and str1[j] == '*'): str1[i] = 'a' str1[j] = 'a' # If only str1[j] = '*' then update it # with the value at str1[i] elif (str1[j] == '*'): str1[j] = str1[i] # If only str1[i] = '*' then update it # with the value at str1[j] elif (str1[i] == '*'): str1[i] = str1[j] # If characters at both positions # are not equal and != '*' then the string # cannot be made palindrome elif (str1[i] != str1[j]): str1 = '' . join(str1) return "-1" i += 1 j -= 1 # Return the required palindrome str1 = '' . join(str1) return str1 # Driver code if __name__ == '__main__': str1 = "na*an" print(makePalindrome(str1)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the lexicographically
// smallest palindrome that can be made from
// the given string after replacing
// the required characters
static String makePalindrome(char[] str)
{
int i = 0, j = str.Length - 1;
while (i <= j)
{
// If characters are missing at both the positions
// then substitute it with 'a'
if (str[i] == '*' && str[j] == '*')
{
str[i] = 'a';
str[j] = 'a';
}
// If only str[j] = '*' then update it
// with the value at str[i]
else if (str[j] == '*')
str[j] = str[i];
// If only str[i] = '*' then update it
// with the value at str[j]
else if (str[i] == '*')
str[i] = str[j];
// If characters at both positions
// are not equal and != '*' then the string
// cannot be made palindrome
else if (str[i] != str[j])
return "-1";
i++;
j--;
}
// Return the required palindrome
return String.Join("",str);
}
// Driver code
public static void Main(String[] args)
{
char[] str = "na*an".ToCharArray();
Console.WriteLine(makePalindrome(str));
}
}
// This code has been contributed by 29AjayKumar
PHP
<?php
// PHP implementation of the approach
// Function to return the lexicographically
// smallest palindrome that can be made from
// the given string after replacing
// the required characters
function makePalindrome($str)
{
$i = 0; $j = strlen($str) - 1;
while ($i <= $j)
{
// If characters are missing at both the positions
// then substitute it with 'a'
if ($str[$i] == '*' && $str[$j] == '*')
{
$str[$i] = 'a';
$str[$j] = 'a';
}
// If only str[j] = '*' then update it
// with the value at str[i]
else if ($str[$j] == '*')
$str[$j] = $str[$i];
// If only str[i] = '*' then update it
// with the value at str[j]
else if ($str[$i] == '*')
$str[$i] = $str[$j];
// If characters at both positions
// are not equal and != '*' then the string
// cannot be made palindrome
else if ($str[$i] != $str[$j])
return "-1";
$i++;
$j--;
}
// Return the required palindrome
return $str;
}
// Driver code
$str = "na*an";
echo makePalindrome($str);
// This Code is contributed by AnkitRai01
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the lexicographically
// smallest palindrome that can be made from
// the given string after replacing
// the required characters
function makePalindrome(str)
{
var i = 0, j = str.length - 1;
while (i <= j) {
// If characters are missing at both the positions
// then substitute it with 'a'
if (str[i] == '*' && str[j] == '*') {
str[i] = 'a';
str[j] = 'a';
}
// If only str[j] = '*' then update it
// with the value at str[i]
else if (str[j] == '*')
str[j] = str[i];
// If only str[i] = '*' then update it
// with the value at str[j]
else if (str[i] == '*')
str[i] = str[j];
// If characters at both positions
// are not equal and != '*' then the string
// cannot be made palindrome
else if (str[i] != str[j])
return "-1";
i++;
j--;
}
// Return the required palindrome
return str.join("");
}
// Driver code
var str = "na*an".split('');
document.write(makePalindrome(str));
</script>
Producción:
naaan
Publicación traducida automáticamente
Artículo escrito por Naman_Garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA