How to check if permutation of a string is a palindrome

Question

Im new to python and im trying to check if any permutation of a string is a palindrome. Here is my code:

def isPal(s):
    a = set()
    for i in s:
        if i in a:
            a.remove(i)
        else:
            if (i != '\n') or (i != ' '):
                a.add(i)
    if len(a) <= 1:
        print(s + ' is a palindrome permutation\n')
    else:
        print(s + ' is not a palindrome permutation\n')
     print(a)

The problem I am having is that it I dont want my set to include spaces or any puncuation thats in the string. Is there any way to only check the letters? For example, the string "Mr. owl ate my Metal worm" shouldnt use the period or spaces when checking if it is a palindrome.

Can't you just check the counts of each letter? If at most 1 has an odd count, then a palindrome must exist. Seems better than checking all permutations. — pault, Mar 29 '19 at 19:29
import re regex = re.compile('[^a-zA-Z]') def is_pal(string): # Remove non-letters regex.sub('', string) # Return True if string is equal to itself backwards. return string == string[::-1] — Greg, Mar 29 '19 at 19:38
@pault How would I do that? would I need another function for counting the letters? — jordan neely, Mar 29 '19 at 19:39
@Prune the question wasn't whether a string is a palindrome or not, but whether it has a permutation that is. — Mureinik, Mar 29 '19 at 19:39
I think this might have been closed prematurely. I believe the question is does *any* permutation exist, not is this exact string palendromic. paults solution will work if that's the case. You can use collections.Counter to count the letters. — Jon Betts, Mar 29 '19 at 19:40
@jordanneely ping me if this question gets reopened, but here's the psuedo code. 1) remove all non-alpha characters using `str.isalpha()` 2) count the occurences of each letter in the string 3) check how many have an odd count 4) if the # of odd is 0 or 1, return True otherwise False — pault, Mar 29 '19 at 19:41
@pault it looks like it is back open. I'm close, just need to remove the punctuations. — jordan neely, Mar 29 '19 at 19:47
@pault et alia -- my mistake; the question is reopened. I assumed that OP had misused the term "permutation", since that problem is *soooooo* easy to solve -- *if* you think it terms of `Counter` structures. My apologies. — Prune, Mar 29 '19 at 19:48
@Prune sorry for being so dumb since I am just starting python and have questions about it. — jordan neely, Mar 29 '19 at 19:50
Nooo! I'm poking fun at myself for making successive invalid assumptions. Each of us has a learning curve, and my assumption is -- well, to put it mildly, I'd have to delete myself for being out of scope. — Prune, Mar 29 '19 at 19:51
Do look at the `collections` module, type `Counter`. @pault has already given you the algorithm; I'm hopeful of seeing that posted as an answer, any minute now. The existing answer is a clone thereof. — Prune, Mar 29 '19 at 19:54

score 5 · Accepted Answer · answered Mar 29 '19 at 19:55

You can certainly check all permutations, but there is a much more efficient approach.

Note that in order for a string to be a palindrome, then every letter is mirrored around the center of the string. That means a collection of letters can form a palindrome if there is at most one letter that has an odd count.

Here is how you can implement this:

The first step is to convert the string to lower case and remove the nonalpha characters (like spaces and punctuation). We can do that by using a list comprehension to iterate over each character in the string and keep only those where str.isalpha() returns True.

myString = "Mr. owl ate my Metal worm"
alpha_chars_only = [x for x in myString.lower() if x.isalpha()]
print(alpha_chars_only)
#['m', 'r', 'o', 'w', 'l', 'a', 't', 'e', 'm', 'y', 'm', 'e', 't', 'a', 'l', 'w', 'o', 'r', 'm']

Next count each letter. You can use collections.Counter for this:

from collections import Counter 
counts = Counter(alpha_chars_only)
print(counts)
#Counter({'m': 4, 'a': 2, 'e': 2, 'l': 2, 'o': 2, 'r': 2, 't': 2, 'w': 2, 'y': 1})

Finally count the number of letters that have an odd count. If the count is 0 or 1, a palindrome must be possible.

number_of_odd = sum(1 for letter, cnt in counts.items() if cnt%2)
print(number_of_odd)
#1

Putting that all together, you can make a function:

def any_palindrome(myString):
    alpha_chars_only = [x for x in myString.lower() if x.isalpha()]
    counts = Counter(alpha_chars_only)
    number_of_odd = sum(1 for letter, cnt in counts.items() if cnt%2)
    return number_of_odd <= 1

print(any_palindrome(mystring))
#True

score 1 · Answer 2 · edited Dec 13 '19 at 06:30

To illustrate further "pythonic" programming, I'm "refining" pault's answer.

def any_palindrome(myString):
    alpha_chars_only = [x for x in myString.lower() if x.isalpha()]
    counts = Counter(alpha_chars_only)
    number_of_odd = sum(1 for letter, cnt in counts.items() if cnt%2)
    return number_of_odd <= 1

Don't be so heavy-handed with the Boolean logic: just add up how many "not even" results you get directly from %:
```
number_of_odd = sum(cnt%2 for cnt in counts.values())
```
Now, plug that directly into the comparison to return:
```
return sum(cnt%2 for cnt in counts.values()) <= 1
```

Build the Counter directly from the input string:

counts = Counter(x for x in myString.lower() if x.isalpha())

Now, combine the two remaining lines into a direct expression:

return sum(cnt%2 for cnt in 
                 Counter(x for x in myString.lower()
                          if x.isalpha()).values()) <= 1

One statement instead of four. Isn't that better?

No, it isn't ... it's hard to read. But you may want to employ these techniques from time to time as you climb up that learning curve.

Head-slap! I intended to write it that way, but was coding a "count the evens" expression in my interleaved task. — Prune, Mar 29 '19 at 20:28
you dont need to use a list comprehension inside the counter. You can see in my solution that a generator will work fine. You can also get rid of the letter,cnt and just use the Counter.values() instead to get a list of counts only. — Grant Williams, Mar 29 '19 at 20:53

Grant Williams · Answer 3 · 2019-03-29T19:58:56.617

I think you can just do something like this:

from string import ascii_letters
from collections import Counter
s = "Mr. owl ate my Metal worm"

def is_permutation_palindrome(s):
 return len([i for i in Counter(c.lower() for c in s if c in ascii_letters).values() if i&1]) < 2

print(is_permutation_palindrome(s))

You have a Counter structure that keeps the count of the lowercase version of each letter and you simply return True if the number of letters with an odd count is 1 or less.

Here is a less compressed version of the code that should be easier to understand and doesnt use any imports:

s = "Mr. owl ate my Metal worm"
def is_permutation_palindrome(s):
    counts = {}
    for c in s.lower():
        if c.isalpha():
            if c in counts:
                counts[c] += 1
            else:
                counts[c] = 1

    odd_counts = [count for count in counts.values() if count % 2 == 1]
    return len(odd_counts) < 2

I wrote it as a one liner because i was planning on posting it in the comments, but you can easily make it a little more readable too. — Grant Williams, Mar 29 '19 at 19:50

score 0 · Answer 4 · answered Jul 03 '19 at 20:29

I though of a very simple function to check if it's a permutation of a palindrome. Basically, a palindrome has to have maximum of one odd letter (the middle one). So basically the function checks if the letter in string is dividable by 2, if it's not then it's incrementing odd letter counter. Then if the odd counter is higher then 1 it's going to return False, meaning that that string cannot be a permutation of palindrome.

def is_palindrome(s):
    odd_counter = 0
    for letter in s:
        if s.count(letter) % 2 != 0:
            odd_counter += 1

    if odd_counter > 1:
        return False
    return True

score 0 · Answer 5 · answered Dec 08 '19 at 18:06

All we need to look for is a character with odd frequency, in this case, using a counter object is very useful instead of calculating the count the frequency of each character in the string we can have a counter object for the string with the frequency for every character in the string. From the values of the counter object, we can determine if more than one character with an odd frequency which makes the string not possible to be a palindrome.

from collections import Counter

def permutationPalindrome(string):
    counterObject = Counter(char for char in string.lower() if char.isalpha())
    no_of_odd = 0
    for value in counterObject.values():
        if value % 2 != 0:
            no_of_odd += 1
        if(no_of_odd > 1):
            return False
    return True

What insight does this add to, say, [Prune's answer](https://stackoverflow.com/a/55424995) the day the question was asked? — greybeard, Dec 08 '19 at 18:33

score 0 · Answer 6 · answered Mar 16 '20 at 18:18

By java, it will take O(N)

   public static int getNumberChar(char temp){
    int a = Character.getNumericValue('a');
    int z = Character.getNumericValue('z');
    int val = Character.getNumericValue(temp);
    if(val >= a && val <= z){
     //   System.out.println("val = " + (val - a));
        return val - a;
    }
    return -1;
}


public static int[] frequencyForEachCharInString(String str){
    int[] frequencyChar = new int[getNumberChar('z')-getNumberChar('a') +1 ];
    for (char c: str.toCharArray()) {
        if(getNumberChar(c) != -1){
          //  System.out.println("c = " + getNumberChar(c));
            frequencyChar[getNumberChar(c)]++;
        }
    }
    return frequencyChar;
}
public static boolean checkIfMaxOneOdd(int[] arr){
    boolean isMaxOddOneOnly = false;
    for (int index: arr) {
        if(index % 2 == 1){
            if(isMaxOddOneOnly){
                return false;
            } // that's mean i found more than one's odd in array ...
            isMaxOddOneOnly =true;
        }
    }
    return true;
}


public static boolean palindromePermutation(String str){
    int[] arr  = frequencyForEachCharInString(str);
    return checkIfMaxOneOdd(arr);

}

score 0 · Answer 7 · answered Mar 25 '21 at 00:00

String palindromePermutation(String s){

      Set<Character> set=new HashSet<Character>();
     
      for(int i=0; i<s.length(); ++i){
        if (!set.contains(s.charAt(i)))
            set.add(s.charAt(i));
        else 
            set.remove(s.charAt(i));
    }
    if(set.size() > 1){
      return "NO";
    }
     return "YES";

  }

score 0 · Answer 8 · answered Mar 30 '22 at 10:02

In order to check whether the permutation of string is palindrome or not, one can achieve it in theta(n) using the below logic

Theoretical Explanation

If there is one character with atmost one odd occurrence then the given string's permutation is palindrome. This also implies that if all characters of the string has even occurrence then also condition will stand.

Practical Code

from collections import Counter

def perm_palindrome(string_input):

    count_dict = Counter(string_input)
    odd_count = 0

    for values in count_dict.values():
        if values % 2 != 0:
            odd_count += 1
            if odd_count > 1:
                return False
    else:
        return True


string_value = "aabb"
output = perm_palindrome(string_input=string_value)
print("Answer of permutation palindrome if {} is :::: {}".format(string_value, output))

Explanation of Time complexity

Counter function in the code will take theta(n)
for loop in the code can run till length of the string if all characters in the string are distinct, hence it can take maximum if theta(n)
So overall time complexity is time complexity of counter function and for loop which will be theta(n) + theta(n) = 2*theta(n)
Constant has no significance when computing the time complexity, hence overall time complexity would be theta(n)

score 0 · Answer 9 · answered Jun 26 '22 at 11:32

Solution with JAVA

import java.util.*;
import java.lang.*;
//Classs
class Permutation {

  /*
   *  We need to have an even number of almost all characters, 
   *  so that half can be on one side and half can be on the other side.
   *  At most one character (the middle character) can have an odd count.
   */
  public static boolean hasPalindrome(String str) {

    boolean wasOdd = false;
    for (Character c: str.toCharArray()) {

      int counter = 0;
      for (Character cc: str.toCharArray()) {
        if (c == cc) {
          counter++;
        }
      }

      if (counter % 2 == 1) {
        if (wasOdd) {
          return false;
        }
        wasOdd = true;
      }
    }


    return true;

  }
  public static void main(String args[]) throws Exception {


    //Taking string input 
    //Scanner
    Scanner s = new Scanner(System.in);
    String str = s.nextLine();
    if (Permutation.hasPalindrome(str)) {
      System.out.println("YES"); // Writing output to STDOUT

    } else {
      System.out.println("NO"); // Writing output to STDOUT


    }


  }
}

vinita gangwani · Answer 10 · 2022-07-01T04:39:12.473

Here I thought of a simple easy to understand python solution. I am making a list of characters whose count comes as odd. If only 1 char is odd then it can fall in between of all the characters thus making it palindrome. Number of odds greater than 1 will make it a non palindrome string.

 def isPermutationOfPalindrome(phrase): #solution in O(l) where l is the length of phrase
        phrase = phrase.lower()
        odd_chars = []
        for rec in phrase:
            if rec!=' ':
                if rec not in odd_chars:
                    odd_chars.append(rec)
                else:
                    odd_chars.remove(rec)
        if(len(odd_chars)<=1):
            return True
        return False
    
    print(isPermutationOfPalindrome("Tact Coa"))

Tracking of Code:

  t  -->  odd_chars =  ['t']
  a  -->  odd_chars =  ['t', 'a']
  c  -->  odd_chars =  ['t', 'a', 'c']
  t  -->  odd_chars =  ['a', 'c']
  c  -->  odd_chars =  ['a']
  o  -->  odd_chars =  ['a', 'o']
  a  -->  odd_chars =  ['o']
    
    Result:
        True

How to check if permutation of a string is a palindrome

10 Answers10