CODEWITHSUNDEEP
python
jordan neely
jordan neely

Reputation: 39

How to check if permutation of a string is a palindrome

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.

Upvotes: 1

Views: 9857

Answers (10)

vinita gangwani
vinita gangwani

Reputation: 1

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

Upvotes: 0

geobudex
geobudex

Reputation: 566

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


    }


  }
}

Upvotes: 0

Sanpreet
Sanpreet

Reputation: 103

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)

Upvotes: 0

Purva
Purva

Reputation: 411

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";

  }

Upvotes: 0

lio
lio

Reputation: 459

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);

}

Upvotes: 0

Prune
Prune

Reputation: 77847

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.

Upvotes: 1

knownstranger
knownstranger

Reputation: 11

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

Upvotes: 0

Matt
Matt

Reputation: 91

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

Upvotes: 0

Grant Williams
Grant Williams

Reputation: 1537

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

Upvotes: 0

pault
pault

Reputation: 43504

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

Upvotes: 6

Related Questions