Java solution w/Set, one pass, without counters.


  • 103
    A

    The idea is to iterate over string, adding current character to set if set doesn't contain that character, or removing current character from set if set contains it.
    When the iteration is finished, just return set.size()==0 || set.size()==1.

    set.size()==0 corresponds to the situation when there are even number of any character in the string, and
    set.size()==1 corresponsds to the fact that there are even number of any character except one.

    public class Solution {
        public boolean canPermutePalindrome(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));
            }
            return set.size()==0 || set.size()==1;
        }
    }

  • 23

    Just a shorter alternative:

    public boolean canPermutePalindrome(String s) {
        Set<Character> set=new HashSet<Character>();
        for(int i=0; i<s.length(); ++i)
            if (!set.add(s.charAt(i)))
                set.remove(s.charAt(i));
        return set.size()<=1;
    }
    

  • 0
    A

    neat, thanks :)


  • 0
    W

    This solution is so brilliant! Thank you!


  • 0
    L

    Thank you for the solution. Could you please tell me why "aab" is Palindrome? Appreciate it!


  • 0
    A

    @libralmy
    Hi,
    aab is no way a palindrome, but it is a permutation of some palindrome, namely aba
    Hope this helps.


  • 0
    L

    @ammv Thank you for the explanation.


  • 0
      public boolean canPermutePalindrome(String s) {
           Set<Character> set = new HashSet<>();
           for(char c: s.toCharArray()){
             if(set.contains(c)){
               set.remove(c);
             } else {
               set.add(c); 
             }  
           }
           return set.size()==0 || set.size()==1;
       }

  • 0
    S

    My easy to understand solution

    public class Solution {
        public boolean canPermutePalindrome(String s) {
            int []hash = new int[256];
            for(int i=0; i<s.length(); i++){
                char c = s.charAt(i);
                hash[c]++;
            }
            
            int odd = 0;
            for(int i=0; i<256; i++){
                if (hash[i] % 2 != 0){
                    odd++;
                    if (odd > 1) 
                        return false;
                }
            }
            return true;
        }
    }
    

  • 0

    @sunnyvale Almost same as yours. But wow, this w/set-without-counter solution is shorter and elegant!

        public boolean canPermutePalindrome(String s) {
            Set<Character> freq = new HashSet<>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);   // Suppose palindrome only contains letter, no space,digits..
                if (!Character.isLetter(c)) continue;
                if (!freq.remove(c)) freq.add(c);
            }
            return freq.size() <= 1;    // At most one odd character
        }
    

  • 0

    @ammv same basic idea, but no need to use a Set. Keep counter of number of chars that have an odd count, update counter as you go, only 1 pass.

        public bool CanPermutePalindrome(string s) {
            int[] map = new int[256];
            int oddCnt = 0;
            foreach (char c in s) oddCnt += (++map[c] & 1) == 1 ? 1 : -1;
            return oddCnt <= 1;
        }
    

  • 0

    Also one pass here, beats 85%.

    public boolean canPermutePalindrome(String s) {
            int[] map = new int[128];
            int odd = 0;
            for (char c : s.toCharArray()) {
                if ((++map[c] & 1) == 1) odd++;
                else if ((map[c] & 1) == 0) odd--;
            }
            return odd == 0 || odd == 1;
        }
    

  • 0
    D

    Can somebody help me to understand the time taken by the above Java code is less by 1ms than the below c++ code?

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


  • 0
    L

    Mine:

    class Solution {
        public boolean canPermutePalindrome(String s) {
            int oddCount = 0;
            boolean[] exists = new boolean[128];
            
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (exists[c]) {
                    oddCount--;
                } else {
                    oddCount++;
                }
                exists[c] = !exists[c];
            }
            
            return oddCount <= 1;
        }
    }
    

Log in to reply
 

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