Dada una string, compruebe si los caracteres de la string dada se pueden reorganizar para formar un palíndromo.
Por ejemplo, los caracteres de «geeksogeeks» se pueden reorganizar para formar un palíndromo «geeksoskeeg», pero los caracteres de «geeksforgeeks» no se pueden reorganizar para formar un palíndromo.
Un conjunto de caracteres puede formar un palíndromo si, como máximo, un carácter aparece un número impar de veces y todos los caracteres aparecen un número par de veces.
Una solución simple es ejecutar dos ciclos, el ciclo externo selecciona todos los caracteres uno por uno y el ciclo interno cuenta el número de ocurrencias del carácter seleccionado. Realizamos un seguimiento de los recuentos impares. La complejidad temporal de esta solución es O(n 2 ).
Podemos hacerlo en tiempo O(n) usando una array de conteo. Los siguientes son pasos detallados.
- Cree una array de conteo de tamaño alfabético que normalmente es 256. Inicialice todos los valores de la array de conteo como 0.
- Recorre la string dada e incrementa el conteo de cada carácter.
- Atraviese la array de conteo y, si la array de conteo tiene más de un valor impar, devuelva falso. De lo contrario, devuelve verdadero.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation to check if
// characters of a given string can
// be rearranged to form a palindrome
#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
/* function to check whether
characters of a string can form a palindrome */
bool canFormPalindrome(string str)
{
// Create a count array and initialize all
// values as 0
int count[NO_OF_CHARS] = { 0 };
// For each character in input strings,
// increment count in the corresponding
// count array
for (int i = 0; str[i]; i++)
count[str[i]]++;
// Count odd occurring characters
int odd = 0;
for (int i = 0; i < NO_OF_CHARS; i++) {
if (count[i] & 1)
odd++;
if (odd > 1)
return false;
}
// Return true if odd count is 0 or 1,
return true;
}
/* Driver code*/
int main()
{
canFormPalindrome("geeksforgeeks")
? cout << "Yes\n"
: cout << "No\n";
canFormPalindrome("geeksogeeks")
? cout << "Yes\n"
: cout << "No\n";
return 0;
}
Java
// Java implementation to check if
// characters of a given string can
// be rearranged to form a palindrome
import java.io.*;
import java.math.*;
import java.util.*;
class GFG {
static int NO_OF_CHARS = 256;
/* function to check whether characters
of a string can form a palindrome */
static boolean canFormPalindrome(String str)
{
// Create a count array and initialize all
// values as 0
int count[] = new int[NO_OF_CHARS];
Arrays.fill(count, 0);
// For each character in input strings,
// increment count in the corresponding
// count array
for (int i = 0; i < str.length(); i++)
count[(int)(str.charAt(i))]++;
// Count odd occurring characters
int odd = 0;
for (int i = 0; i < NO_OF_CHARS; i++) {
if ((count[i] & 1) == 1)
odd++;
if (odd > 1)
return false;
}
// Return true if odd count is 0 or 1,
return true;
}
// Driver code
public static void main(String args[])
{
if (canFormPalindrome("geeksforgeeks"))
System.out.println("Yes");
else
System.out.println("No");
if (canFormPalindrome("geeksogeeks"))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Nikita Tiwari.
Python3
# Python3 implementation to check if
# characters of a given string can
# be rearranged to form a palindrome
NO_OF_CHARS = 256
# function to check whether characters
# of a string can form a palindrome
def canFormPalindrome(st):
# Create a count array and initialize
# all values as 0
count = [0] * (NO_OF_CHARS)
# For each character in input strings,
# increment count in the corresponding
# count array
for i in range(0, len(st)):
count[ord(st[i])] = count[ord(st[i])] + 1
# Count odd occurring characters
odd = 0
for i in range(0, NO_OF_CHARS):
if (count[i] & 1):
odd = odd + 1
if (odd > 1):
return False
# Return true if odd count is 0 or 1,
return True
# Driver code
if(canFormPalindrome("geeksforgeeks")):
print("Yes")
else:
print("No")
if(canFormPalindrome("geeksogeeks")):
print("Yes")
else:
print("No")
# This code is contributed by Nikita Tiwari.
C#
// C# implementation to check if
// characters of a given string can
// be rearranged to form a palindrome
using System;
class GFG {
static int NO_OF_CHARS = 256;
/* function to check whether characters
of a string can form a palindrome */
static bool canFormPalindrome(string str)
{
// Create a count array and initialize all
// values as 0
int[] count = new int[NO_OF_CHARS];
Array.Fill(count, 0);
// For each character in input strings,
// increment count in the corresponding
// count array
for (int i = 0; i < str.Length; i++)
count[(int)(str[i])]++;
// Count odd occurring characters
int odd = 0;
for (int i = 0; i < NO_OF_CHARS; i++) {
if ((count[i] & 1) == 1)
odd++;
if (odd > 1)
return false;
}
// Return true if odd count is 0 or 1,
return true;
}
// Driver code
public static void Main()
{
if (canFormPalindrome("geeksforgeeks"))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
if (canFormPalindrome("geeksogeeks"))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
Javascript
<script>
// Javascript implementation to check if
// characters of a given string can
// be rearranged to form a palindrome
let NO_OF_CHARS = 256;
/* function to check whether characters
of a string can form a palindrome */
function canFormPalindrome(str)
{
// Create a count array and initialize all
// values as 0
let count = Array(NO_OF_CHARS).fill(0);
// For each character in input strings,
// increment count in the corresponding
// count array
for (let i = 0; i < str.length; i++)
count[str[i].charCodeAt()]++;
// Count odd occurring characters
let odd = 0;
for (let i = 0; i < NO_OF_CHARS; i++) {
if ((count[i] & 1) == 1)
odd++;
if (odd > 1)
return false;
}
// Return true if odd count is 0 or 1,
return true;
}
// Driver program
if (canFormPalindrome("geeksforgeeks"))
document.write("Yes");
else
document.write("No");
if (canFormPalindrome("geeksogeeks"))
document.write("Yes");
else
document.write("No");
</script>
Producción
No Yes
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. Donde N es la longitud de la string.
Espacio auxiliar: O (256), ya que estamos usando espacio adicional para el recuento de arrays .
Este artículo es una contribución de Abhishek. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Otro enfoque:
podemos hacerlo en tiempo O(n) usando una lista. Los siguientes son pasos detallados.
- Crea una lista de personajes.
- Recorre la string dada.
- Para cada carácter de la string, elimine el carácter si la lista ya contiene algo más para agregar a la lista.
- Si la longitud de la string es par, se espera que la lista esté vacía.
- O si la longitud de la string es impar, se espera que el tamaño de la lista sea 1
- En las dos condiciones anteriores (3) o (4) devuelva verdadero; de lo contrario, devuelva falso.
C++
#include <bits/stdc++.h>
using namespace std;
/*
* function to check whether characters of
a string can form a palindrome
*/
bool canFormPalindrome(string str)
{
// Create a list
vector<char> list;
// For each character in input strings,
// remove character if list contains
// else add character to list
for (int i = 0; i < str.length(); i++)
{
auto pos = find(list.begin(),
list.end(), str[i]);
if (pos != list.end()) {
auto posi
= find(list.begin(),
list.end(), str[i]);
list.erase(posi);
}
else
list.push_back(str[i]);
}
// if character length is even list is
// expected to be empty or if character
// length is odd list size is expected to be 1
// if string length is even
if (str.length() % 2 == 0
&& list.empty()
|| (str.length() % 2 == 1
&& list.size() == 1))
return true;
// if string length is odd
else
return false;
}
// Driver code
int main()
{
if (canFormPalindrome("geeksforgeeks"))
cout << ("Yes") << endl;
else
cout << ("No") << endl;
if (canFormPalindrome("geeksogeeks"))
cout << ("Yes") << endl;
else
cout << ("No") << endl;
}
// This code is contributed by Rajput-Ji
Java
import java.util.ArrayList;
import java.util.List;
class GFG {
/*
* function to check whether
* characters of a string can form a palindrome
*/
static boolean canFormPalindrome(String str)
{
// Create a list
List<Character> list = new ArrayList<Character>();
// For each character in input strings,
// remove character if list contains
// else add character to list
for (int i = 0; i < str.length(); i++)
{
if (list.contains(str.charAt(i)))
list.remove((Character)str.charAt(i));
else
list.add(str.charAt(i));
}
// if character length is even
// list is expected to be empty or
// if character length is odd list size
// is expected to be 1
// if string length is even
if (str.length() % 2 == 0
&& list.isEmpty()
|| (str.length() % 2 == 1
&& list.size()
== 1))
return true;
// if string length is odd
else
return false;
}
// Driver code
public static void main(String args[])
{
if (canFormPalindrome("geeksforgeeks"))
System.out.println("Yes");
else
System.out.println("No");
if (canFormPalindrome("geeksogeeks"))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Sugunakumar P
Python3
'''
* function to check whether characters of
a string can form a palindrome
'''
def canFormPalindrome(strr):
# Create a list
listt = []
# For each character in input strings,
# remove character if list contains
# else add character to list
for i in range(len(strr)):
if (strr[i] in listt):
listt.remove(strr[i])
else:
listt.append(strr[i])
# if character length is even
# list is expected to be empty
# or if character length is odd
# list size is expected to be 1
if (len(strr) % 2 == 0 and len(listt) == 0 or
(len(strr) % 2 == 1 and len(listt) == 1)):
return True
else:
return False
# Driver code
if (canFormPalindrome("geeksforgeeks")):
print("Yes")
else:
print("No")
if (canFormPalindrome("geeksogeeks")):
print("Yes")
else:
print("No")
# This code is contributed by SHUBHAMSINGH10
C#
// C# Implementation of the above approach
using System;
using System.Collections.Generic;
class GFG {
/*
* function to check whether characters
of a string can form a palindrome
*/
static Boolean canFormPalindrome(String str)
{
// Create a list
List<char> list = new List<char>();
// For each character in input strings,
// remove character if list contains
// else add character to list
for (int i = 0; i < str.Length; i++)
{
if (list.Contains(str[i]))
list.Remove((char)str[i]);
else
list.Add(str[i]);
}
// if character length is even
// list is expected to be empty
// or if character length is odd
// list size is expected to be 1
// if string length is even
if (str.Length % 2 == 0 && list.Count == 0
||
(str.Length % 2 == 1
&& list.Count == 1))
return true;
// if string length is odd
else
return false;
}
// Driver Code
public static void Main(String[] args)
{
if (canFormPalindrome("geeksforgeeks"))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
if (canFormPalindrome("geeksogeeks"))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
/*
* function to check whether
* characters of a string can form a palindrome
*/
function canFormPalindrome(str)
{
// Create a list
let list = [];
// For each character in input strings,
// remove character if list contains
// else add character to list
for(let i = 0; i < str.length; i++)
{
if (list.includes(str[i]))
list.splice(list.indexOf(str[i]), 1);
else
list.push(str[i]);
}
// If character length is even
// list is expected to be empty or
// if character length is odd list size
// is expected to be 1
// If string length is even
if (str.length % 2 == 0 && list.length == 0 ||
(str.length % 2 == 1 && list.length == 1))
return true;
// If string length is odd
else
return false;
}
// Driver code
if (canFormPalindrome("geeksforgeeks"))
document.write("Yes<br>");
else
document.write("No<br>");
if (canFormPalindrome("geeksogeeks"))
document.write("Yes<br>");
else
document.write("No<br>");
// This code is contributed by ab2127
</script>
Producción
No Yes
Complejidad de tiempo: O(N*N), ya que estamos usando un ciclo para recorrer N veces y en cada recorrido, estamos usando la función de búsqueda para obtener la posición de un personaje que costará O(N) tiempo. Donde N es la longitud de la string.
Espacio auxiliar: O(N), ya que estamos usando espacio adicional para la lista de arreglos de caracteres . Donde N es la longitud de la string.
Otro enfoque: (usando bits)
Este problema se puede resolver en tiempo O(n) donde n es el número de caracteres en la string y el espacio O(1).
Para que la string sea palíndromo, todos los caracteres deben aparecer un número par de veces si la string tiene una longitud par y, como máximo, un carácter puede aparecer un número impar de veces si la longitud de la string es impar. En su lugar, no se requiere realizar un seguimiento del recuento de caracteres, es suficiente realizar un seguimiento si los recuentos son pares o impares.
Esto se puede lograr usando una variable como vector de bits.
Para cada carácter de la string:
si el bit correspondiente al carácter no está activado: //si es una ocurrencia impar del carácter, establezca el bit
de lo contrario, si el bit correspondiente al carácter está establecido: //si es la ocurrencia par del carácter, cambie el bit
Esto es similar a realizar una operación XOR entre el vector de bits y la máscara.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Implementation of the above approach
# include <bits/stdc++.h>
using namespace std;
bool canFormPalindrome(string a)
{
// bitvector to store
// the record of which character appear
// odd and even number of times
int bitvector = 0, mask = 0;
for (int i=0; a[i] != '\0'; i++)
{
int x = a[i] - 'a';
mask = 1 << x;
bitvector = bitvector ^ mask;
}
return (bitvector & (bitvector - 1)) == 0;
}
// Driver Code
int main()
{
if (canFormPalindrome("geeksforgeeks"))
cout << ("Yes") << endl;
else
cout << ("No") << endl;
return 0;
}
Java
// Java Implementation of the above approach
import java.io.*;
class GFG
{
static boolean canFormPalindrome(String a)
{
// bitvector to store
// the record of which character appear
// odd and even number of times
int bitvector = 0, mask = 0;
for (int i = 0; i < a.length(); i++)
{
int x = a.charAt(i) - 'a';
mask = 1 << x;
bitvector = bitvector ^ mask;
}
return (bitvector & (bitvector - 1)) == 0;
}
// Driver Code
public static void main (String[] args) {
if (canFormPalindrome("geeksforgeeks"))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by rag2127
Python3
# Python3 implementation of above approach.
def canFormPalindrome(s):
bitvector = 0
for str in s:
bitvector ^= 1 << ord(str)
return bitvector == 0 or bitvector & (bitvector - 1) == 0
#s = input()
if canFormPalindrome("geeksforgeeks"):
print('Yes')
else:
print('No')
# This code is contributed by sahilmahale0
C#
// C# Implementation of the above approach
using System;
public class GFG
{
static bool canFormPalindrome(string a)
{
// bitvector to store
// the record of which character appear
// odd and even number of times
int bitvector = 0, mask = 0;
for (int i = 0; i < a.Length; i++)
{
int x = a[i] - 'a';
mask = 1 << x;
bitvector = bitvector ^ mask;
}
return (bitvector & (bitvector - 1)) == 0;
}
// Driver Code
static public void Main (){
if (canFormPalindrome("geeksforgeeks"))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// JavaScript implementation of the above approach
function canFormPalindrome(a)
{
// Bitvector to store the record
// of which character appear
// odd and even number of times
var bitvector = 0, mask = 0;
for(var i = 0; i < a.length; i++)
{
var x = a.charCodeAt(i) - 97;
mask = 1 << x;
bitvector = bitvector ^ mask;
}
return ((bitvector & (bitvector - 1)) == 0);
}
// Driver Code
if (canFormPalindrome("geeksforgeeks"))
document.write("Yes" + "<br>");
else
document.write("No" + "<br>");
// This code is contributed by akshitsaxenaa09
</script>
Producción
No
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. Donde N es la longitud de la string.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA