1-4 lines Python, Ruby, C++, C, Java


  • 52

    Just check that no more than one character appears an odd number of times. Because if there is one, then it must be in the middle of the palindrome. So we can't have two of them.

    Python

    First count all characters in a Counter, then count the odd ones.

    def canPermutePalindrome(self, s):
        return sum(v % 2 for v in collections.Counter(s).values()) < 2
    

    Ruby

    Using an integer as a bitset (Ruby has arbitrarily large integers).

    def can_permute_palindrome(s)
      x = s.chars.map { |c| 1 << c.ord }.reduce(0, :^)
      x & x-1 == 0
    end
    

    C++

    Using a bitset.

    bool canPermutePalindrome(string s) {
        bitset<256> b;
        for (char c : s)
            b.flip(c);
        return b.count() < 2;
    }
    

    C

    Tricky one. Increase odds when the increased counter is odd, decrease it otherwise.

    bool canPermutePalindrome(char* s) {
        int ctr[256] = {}, odds = 0;
        while (*s)
            odds += ++ctr[*s++] & 1 ? 1 : -1;
        return odds < 2;
    }
    

    Thanks to jianchao.li.fighter for pointing out a nicer way in the comments to which I switched now because it's clearer and faster. Some speed test results (see comments for details):

            odds += ++ctr[*s++] % 2 * 2 - 1;       // 1499 ms mean-of-five (my original)
            odds += (ctr[*s++] ^= 1) * 2 - 1;      // 1196 ms mean-of-five
            odds += ++ctr[*s++] % 2 ? 1 : -1;      // 1108 ms mean-of-five
            odds += ((++ctr[*s++] & 1) << 1) - 1;  // 1217 ms mean-of-five
            odds += ++ctr[*s++] & 1 ? 1 : -1;      // 1132 ms mean-of-five
    

    Java

    Using a BitSet.

    public boolean canPermutePalindrome(String s) {
        BitSet bs = new BitSet();
        for (byte b : s.getBytes())
            bs.flip(b);
        return bs.cardinality() < 2;
    }

  • 3

    Great code using bitset! Well, I have still not used it before and just learned it from your codes :-) BTW, I happen to have a C++ code using simple hash maps that is very similar to your C version.

    class Solution {
    public:
        bool canPermutePalindrome(string s) {
            int odd = 0, counts[256] = {0};
            for (char c : s)
                odd += ++counts[c] & 1 ? 1 : -1; 
            return odd <= 1;
        }
    };

  • 1

    Yeah, you're right, that's better. I actually saw that and also (ctr[*s++] ^= 1) * 2 - 1, but both were one character longer than ++ctr[*s++] % 2 * 2 - 1, so I kept that :-)

    But the ?: way is clearer and I just tested it, it's apparently also faster on the OJ system:

    bool canPermutePalindrome(char* s) {
        int ctr[256] = {}, odds = 0;
        bool res;
        char* s0 = s;
        for (int i=0; i<100000; ++i) {
            s = s0;
            while (*s)
        //      odds += ++ctr[*s++] % 2 * 2 - 1;       // 1499 ms average-of-five
        //      odds += (ctr[*s++] ^= 1) * 2 - 1;      // 1196 ms average-of-five
        //      odds += ++ctr[*s++] % 2 ? 1 : -1;      // 1108 ms average-of-five
        //      odds += ((++ctr[*s++] & 1) << 1) - 1;  // 1217 ms average-of-five
                odds += ++ctr[*s++] & 1 ? 1 : -1;      // 1132 ms average-of-five
            if (!i)
                res = odds < 2;
        }
        return res;
    }
    

  • 0

    Oh, I just realized I only had the ? 1 : -1 but used % 2 instead of your & 1. I added it to my speed test now and rather oddly, & 1 was slower than % 2. Anyway, I'll add it to my question. Thanks.


  • 0

    Wow, Stefan. Thank you for coming up with so many alternatives and testing them! Oh yeah, it is a little strange that bit operator & is slower than arithmetic operator %. BTW, (ctr[*s++] ^= 1) * 2 - 1 is really cool, getting rid of the ++ in the front :-)


  • 0
    O

    Even the same code can run different performance each time, I wonder if the time testing really shows the efficiency.


  • 0

    @oaknova Yes, I know, that's why I did that 10000-loop and took the average out of five submissions for every version. In case you missed that, it's in comments behind them in the code. And while there was still some variation (I guess I should have posted that as well), I do think it gives a decent picture and allows some conclusions (like that the % 2 * 2 - 1 version is much slower). But you're very welcome to test it some more and show more statistics :-)


  • 0
    O

    Thank you for the reply, I didn't know we can test the time efficiency in this way. It makes sense!


  • 0
    F

    aha, your python solution is exactly what I also come up with:-)


  • 0
    S

    @StefanPochmann Your code always surprised me. Thanks for sharing!


  • 0
    H

    How about this?

    C++ code:

    bool Strings::canPermutePalindrome(string s)
    {
    	for (int i = 0; i < s.length() / 2; ++i)
    	{
    		if (s[i] != s[s.length() - 1 - i]) return false;
    	}
    	return true;
    }

  • 1

    Did something similar:

    from collections import Counter as C
    
    class Solution(object):
        def canPermutePalindrome(self, s):
            return not sum(e % 2 for e in C(s).values()) ^ (len(s) % 2)

  • 0
    M
    This post is deleted!

  • 0
    E

    @humooo
    I don't think your code would pass


  • 0
    S

    Here's a O(n) Python AC solution based on dictionary and bit inversion

    class Solution(object):
        def canPermutePalindrome(self, s):
            """
            :type s: str
            :rtype: bool
            """
            chCount = collections.defaultdict(int)
            for ch in s:
                chCount[ch] ^= 1
            return list(chCount.values()).count(1) < 2
    

  • 0
    I
    This post is deleted!

  • 0
    I

    @jianchao.li.fighter
    class Solution {
    public:
    bool canPermutePalindrome(string s) {
    int odd = 0, counts[256] = {0};
    for (char c : s)
    odd += ++counts[c] & 1 ? 1 : -1;
    return odd <= 1;
    }
    };

    I am so sorry for my question.
    I am very new to programming.
    can you clarify for me what char c: s and ++counts[c] and odd += ++counts[c] & 1 ? 1 : -1; do?
    And how we understand what letter/string is what?


  • 0
    A

    @StefanPochmann The below code is working for all characters, except when it needs to differentiate between lowercase and uppercase letters, its giving true for "Aa", expected OJ answer is false.
    Please advice 1) How its working for all characters when I have defined 32 bit (int) array. 2) While doing left shift, why bit operation is taking same ascii value for lower and upper case Characters.

    public boolean canPermutePalindrome(String s) {
            int a=0;
            char[] charr = s.toCharArray();
            for(char c: charr) a^=(1<<c);
            return (a==0 || (a & (a-1))==0);
        }

  • 0

    @aayushgarg From https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.19:

    If the promoted type of the left-hand operand is int, then only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x1f (0b11111). The shift distance actually used is therefore always in the range 0 to 31, inclusive.


  • 0
    A

    @StefanPochmann Apparently the below code is passing all test cases and accepted by OJ. Requested leetcode team to add missing test cases. The below code will fail for strings with character combination - "!a", "9y", ":z", ">~" etc. where only 7th lsb differs.

        public boolean canPermutePalindrome(String s) {
            long a=0;
            char[] charr = s.toCharArray();
            for(char c: charr) a^=((long)1<<c);
            return (a==0 || (a & (a-1))==0);
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.