Comprobar si algún anagrama de una string es palíndromo o no

Hemos dado una string de anagrama y tenemos que comprobar si se puede hacer palíndromo o no. 
Ejemplos: 

Input : geeksforgeeks 
Output : No
There is no palindrome anagram of 
given string

Input  : geeksgeeks
Output : Yes
There are palindrome anagrams of
given string. For example kgeesseegk

Este problema es básicamente el mismo que Verificar si los caracteres de una string determinada se pueden reorganizar para formar un palíndromo . Podemos hacerlo en tiempo O(n) usando una array de conteo. Los siguientes son pasos detallados. 
1) 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. 
2) Recorra la string dada e incremente el conteo de cada carácter. 
3) 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. 

C++

#include <iostream>
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 program to test to print printDups*/
int main()
{
    canFormPalindrome("geeksforgeeks") ? cout << "Yes\n" : cout << "No\n";
    canFormPalindrome("geeksogeeks") ? cout << "Yes\n" : cout << "No\n";
    return 0;
}

Java

// Java program to Check if any anagram
// of a string is palindrome or not
public class GFG {
    static final 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];
 
        // For each character in input strings,
        // increment count in the corresponding
        // count array
        for (int i = 0; i < str.length(); i++)
            count[str.charAt(i)]++;
 
        // Count odd occurring characters
        int odd = 0;
        for (int i = 0; i < NO_OF_CHARS; i++) {
            if ((count[i] & 1) != 0)
                odd++;
 
            if (odd > 1)
                return false;
        }
 
        // Return true if odd count is 0 or 1,
        return true;
    }
 
    /* Driver program to test to print printDups*/
    public static void main(String args[])
    {
        System.out.println(canFormPalindrome("geeksforgeeks")
                               ? "Yes"
                               : "No");
        System.out.println(canFormPalindrome("geeksogeeks")
                               ? "Yes"
                               : "No");
    }
}
// This code is contributed by Sumit Ghosh

Python

NO_OF_CHARS = 256
   
""" function to check whether characters of a string
   can form a palindrome """
def canFormPalindrome(string):
     
    # Create a count array and initialize all
    # values as 0
    count = [0 for i in range(NO_OF_CHARS)]
   
    # For each character in input strings,
    # increment count in the corresponding
    # count array
    for i in string:
        count[ord(i)] += 1
   
    # Count odd occurring characters
    odd = 0
    for i in range(NO_OF_CHARS):
        if (count[i] & 1):
            odd += 1
  
        if (odd > 1):
            return False
   
    # Return true if odd count is 0 or 1,
    return True
   
# Driver program to test to print printDups
if(canFormPalindrome("geeksforgeeks")):
    print "Yes"
else:
    print "No"
if(canFormPalindrome("geeksogeeks")):
    print "Yes"
else:
    print "NO"
 
# This code is contributed by Sachin Bisht

C#

// C# program to Check if any anagram
// of a string is palindrome or not
using System;
 
public 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];
 
        // For each character in input
        // strings, increment count in
        // the corresponding count array
        for (int i = 0; i < str.Length; i++)
            count[str[i]]++;
 
        // Count odd occurring characters
        int odd = 0;
        for (int i = 0; i < NO_OF_CHARS; i++) {
            if ((count[i] & 1) != 0)
                odd++;
 
            if (odd > 1)
                return false;
        }
 
        // Return true if odd count
        // is 0 or 1,
        return true;
    }
 
    // Driver program
    public static void Main()
    {
        Console.WriteLine(
            canFormPalindrome("geeksforgeeks")
                              ? "Yes" : "No");
                               
        Console.WriteLine(
            canFormPalindrome("geeksogeeks")
                              ? "Yes" : "No");
    }
}
 
// This code is contributed by vt_m.

Javascript

<script>
    // Javascript program to Check if any anagram
    // of a string is palindrome or not
     
    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 = new Array(NO_OF_CHARS);
        count.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) != 0)
                odd++;
  
            if (odd > 1)
                return false;
        }
  
        // Return true if odd count
        // is 0 or 1,
        return true;
    }
     
    document.write(canFormPalindrome("geeksforgeeks")? "Yes" + "</br>" : "No" + "</br>");
                                
      document.write(canFormPalindrome("geeksogeeks")? "Yes" : "No");
 
// This code is contributed by divyeshrabadiya07.
</script>

Producción: 

No
Yes

Complejidad de tiempo : O(n)

Espacio auxiliar : O(n). 

Este artículo es una contribución de Aarti_Rathi y Rishabh Jain . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
  

Método 2:

Usando funciones integradas y lógica/algo de la siguiente manera:

  1. 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.
  2. Recorre la string dada e incrementa el conteo de cada carácter.
  3. Recorra la array de conteo y si la array de conteo tiene más de un valor impar, devuelva falso. De lo contrario, devuelve verdadero.

Podemos usar el módulo de colecciones para reducir el número de líneas de código sin contarlo manualmente usando el diccionario.

Python3

from collections import Counter
def isPossible(S):
        a=Counter(S)
        #create the dictionary of characters which has the count of characters in String
        a=dict(a)
        #print(a)
        c=0
        #Iterate through the values
        for v in a.values():
          # To chech odd or not
            if v%2==1:
                c+=1
        if c>1:
            return False
        return True
# contributed by Raghavendra SN
q=isPossible('geeksogeeks')
print(q)
z=isPossible('geeksforgeeks')
print(z)
Producción

True
False

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *