Dada una string, la tarea es verificar si la string se puede convertir en palíndromo intercambiando un carácter solo una vez.
[NOTA: solo un intercambio y solo un carácter debe intercambiarse con otro carácter]
Ejemplos:
Input : bbg
Output : true
Explanation: Swap b(1st index) with g.
Input : bdababd
Output : true
Explanation: Swap b(0th index) with d(last index) or
Swap d(1st index) with b(second index)
Input : gcagac
Output : false
Acercarse:
Este algoritmo se basó en un análisis exhaustivo del comportamiento y la posibilidad del palíndromo de cuerdas en formación. Mediante este análisis, obtuve las siguientes conclusiones:
1. En primer lugar, encontraremos las diferencias en la cuerda que en realidad evita que sea un palíndromo.
…..a) Para hacer esto, comenzaremos desde ambos extremos y compararemos un elemento de cada extremo a la vez, cada vez que coincida almacenaremos los valores en una array separada ya que junto con esto mantenemos un conteo en el número de artículos inigualables.
2. Si el número de elementos no coincidentes es superior a 2, nunca es posible convertirlo en una string palíndromo intercambiando solo un carácter.
3. Si (número de elementos no coincidentes = 2): es posible hacer el palíndromo de strings si los caracteres presentes en el primer conjunto no coincidente son los mismos que los presentes en el segundo conjunto no coincidente. (Por ejemplo: pruebe esto «bdababd»).
4. Si (número de elementos no emparejados = 1)
…..a) si (la longitud de la string es par), no es posible hacer una string de palíndromo a partir de esto.
…..b) si (la longitud de la string es impar): es posible hacer una string de palíndromo a partir de esto si uno de los caracteres no coincidentes coincide con el carácter del medio.
5. Si (número de elementos no coincidentes = 0), el palíndromo es posible si intercambiamos la posición de los mismos caracteres.
C++
// C++ program palindrome by swapping
// only one character
#include <bits/stdc++.h>
using namespace std;
bool isPalindromePossible(string input)
{
int len = input.length();
// counts the number of differences
// which prevents the string from
// being palindrome.
int diffCount = 0, i;
// keeps a record of the characters
// that prevents the string from
// being palindrome.
char diff[2][2];
// loops from the start of a string
// till the midpoint of the string
for (i = 0; i < len / 2; i++)
{
// difference is encountered preventing
// the string from being palindrome
if (input[i] != input[len - i - 1])
{
// 3rd differences encountered and
// its no longer possible to make
// is palindrome by one swap
if (diffCount == 2) return false;
// record the different character
diff[diffCount][0] = input[i];
// store the different characters
diff[diffCount++][1] = input[len - i - 1];
}
}
switch (diffCount)
{
// its already palindrome
case 0:
return true;
// only one difference is found
case 1:
{
char midChar = input[i];
// if the middleChar matches either of
// the difference producing characters,
// return true
if (len % 2 != 0 and
(diff[0][0] == midChar or
diff[0][1] == midChar))
return true;
}
// two differences are found
case 2:
// if the characters contained in
// the two sets are same, return true
if ((diff[0][0] == diff[1][0] and
diff[0][1] == diff[1][1]) or
(diff[0][0] == diff[1][1] and
diff[0][1] == diff[1][0]))
return true;
}
return false;
}
// Driver Code
int main()
{
cout << boolalpha
<< isPalindromePossible("bbg") << endl;
cout << boolalpha
<< isPalindromePossible("bdababd") << endl;
cout << boolalpha
<< isPalindromePossible("gcagac") << endl;
return 0;
}
// This code is contributed by
// sanjeev2552
Java
// Java program palindrome by swapping
// only one character
class GFG
{
public static boolean isPalindromePossible(String input)
{
// convert the string to character array
char[] charStr = input.toCharArray();
int len = input.length(), i;
// counts the number of differences which prevents
// the string from being palindrome.
int diffCount = 0;
// keeps a record of the characters that prevents
// the string from being palindrome.
char[][] diff = new char[2][2];
// loops from the start of a string till the midpoint
// of the string
for (i = 0; i < len / 2; i++) {
// difference is encountered preventing the string
// from being palindrome
if (charStr[i] != charStr[len - i - 1]) {
// 3rd differences encountered and its no longer
// possible to make is palindrome by one swap
if (diffCount == 2)
return false;
// record the different character
diff[diffCount][0] = charStr[i];
// store the different characters
diff[diffCount++][1] = charStr[len - i - 1];
}
}
switch (diffCount) {
// its already palindrome
case 0:
return true;
// only one difference is found
case 1:
char midChar = charStr[i];
// if the middleChar matches either of the
// difference producing characters, return true
if (len % 2 != 0 && (diff[0][0] == midChar
|| diff[0][1] == midChar))
return true;
// two differences are found
case 2:
// if the characters contained in the two sets are same,
// return true
if ((diff[0][0] == diff[1][0] && diff[0][1] == diff[1][1])
|| (diff[0][0] == diff[1][1] && diff[0][1] == diff[1][0]))
return true;
}
return false;
}
public static void main(String[] args)
{
System.out.println(isPalindromePossible("bbg"));
System.out.println(isPalindromePossible("bdababd"));
System.out.println(isPalindromePossible("gcagac"));
}
}
Python3
# Python3 program palindrome by swapping
# only one character
def isPalindromePossible(input: str) -> bool:
length = len(input)
# counts the number of differences
# which prevents the string from
# being palindrome.
diffCount = 0
i = 0
# keeps a record of the characters
# that prevents the string from
# being palindrome.
diff = [['0'] * 2] * 2
# loops from the start of a string
# till the midpoint of the string
while i < length // 2:
# difference is encountered preventing
# the string from being palindrome
if input[i] != input[length - i - 1]:
# 3rd differences encountered and
# its no longer possible to make
# is palindrome by one swap
if diffCount == 2:
return False
# record the different character
diff[diffCount][0] = input[i]
# store the different characters
diff[diffCount][1] = input[length - i - 1]
diffCount += 1
i += 1
# its already palindrome
if diffCount == 0:
return True
# only one difference is found
elif diffCount == 1:
midChar = input[i]
# if the middleChar matches either of
# the difference producing characters,
# return true
if length % 2 != 0 and (diff[0][0] == midChar
or diff[0][1] == midChar):
return True
# two differences are found
elif diffCount == 2:
# if the characters contained in
# the two sets are same, return true
if (diff[0][0] == diff[1][0] and diff[0][1] == diff[1][1]) or (
diff[0][0] == diff[1][1] and diff[0][1] == diff[1][0]):
return True
return False
# Driver Code
if __name__ == "__main__":
print(isPalindromePossible("bbg"))
print(isPalindromePossible("bdababd"))
print(isPalindromePossible("gcagac"))
# This code is contributed by
# sanjeev2552
C#
// C# program palindrome by swapping
// only one character
using System;
class GFG
{
public static bool isPalindromePossible(String input)
{
// convert the string to character array
char[] charStr = input.ToCharArray();
int len = input.Length, i;
// counts the number of differences
// which prevents the string
// from being palindrome.
int diffCount = 0;
// keeps a record of the
// characters that prevents
// the string from being palindrome.
char[,] diff = new char[2, 2];
// loops from the start of a string
// till the midpoint of the string
for (i = 0; i < len / 2; i++)
{
// difference is encountered preventing
// the string from being palindrome
if (charStr[i] != charStr[len - i - 1])
{
// 3rd differences encountered
// and its no longer possible to
// make is palindrome by one swap
if (diffCount == 2)
return false;
// record the different character
diff[diffCount, 0] = charStr[i];
// store the different characters
diff[diffCount++, 1] = charStr[len - i - 1];
}
}
switch (diffCount)
{
// its already palindrome
case 0:
return true;
// only one difference is found
case 1:
char midChar = charStr[i];
// if the middleChar matches either of the
// difference producing characters, return true
if (len % 2 != 0 &&
(diff[0,0] == midChar ||
diff[0,1] == midChar))
return true;
break;
// two differences are found
case 2:
// if the characters contained in
// the two sets are same, return true
if ((diff[0,0] == diff[1,0] &&
diff[0,1] == diff[1,1]) ||
(diff[0,0] == diff[1,1] &&
diff[0,1] == diff[1,0]))
return true;
break;
}
return false;
}
// Driver code
public static void Main(String[] args)
{
Console.WriteLine(isPalindromePossible("bbg"));
Console.WriteLine(isPalindromePossible("bdababd"));
Console.WriteLine(isPalindromePossible("gcagac"));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program palindrome by swapping
// only one character
function isPalindromePossible(input){
let Length = input.length
// counts the number of differences
// which prevents the string from
// being palindrome.
let diffCount = 0,i = 0
// keeps a rec||d of the characters
// that prevents the string from
// being palindrome.
let diff = new Array(2).fill(0).map(()=>new Array(2))
// loops from the start of a string
// till the midpoint of the string
for (i = 0; i < Math.floor(Length / 2); i++)
{
// difference is encountered preventing
// the string from being palindrome
if(input[i] != input[Length - i - 1]){
// 3rd differences encountered &&
// its no longer possible to make
// is palindrome by one swap
if(diffCount == 2)
return false
// rec||d the different character
diff[diffCount][0] = input[i]
// st||e the different characters
diff[diffCount++][1] = input[Length - i - 1]
}
}
switch (diffCount)
{
// its already palindrome
case 0:
return true
// only one difference is found
case 1:
{
let midChar = input[i]
// if the middleChar matches either of
// the difference producing characters,
// return true
if (Length % 2 != 0 &&
(diff[0][0] == midChar ||
diff[0][1] == midChar))
return true
}
// two differences are found
case 2:
// if the characters contained in
// the two sets are same, return true
if ((diff[0][0] == diff[1][0] &&
diff[0][1] == diff[1][1]) ||
(diff[0][0] == diff[1][1] &&
diff[0][1] == diff[1][0]))
return true
}
return false
}
// driver code
document.write(isPalindromePossible("bbg"),"</br>")
document.write(isPalindromePossible("bdababd"),"</br>")
document.write(isPalindromePossible("gcagac"),"</br>")
// This code is contributed by shinjanpatra
</script>
Producción:
true true false
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por Prasun Mondal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA