Question

Formatted question description: https://leetcode.ca/all/266.html

 266	Palindrome Permutation

 Given a string, determine if a permutation of the string could form a palindrome.

 For example,
 "code" -> False, "aab" -> True, "carerac" -> True.


 Hint:

 Consider the palindromes of odd vs even length. What difference do you notice?
 Count the frequency of each character.
 If each character occurs even number of times, then it must be a palindrome.
    How about character which occurs odd number of times?

Algorithm

Use HashSet to traverse the string

If a letter is not in the HashSet, we add this letter,
If the letter already exists, we delete the letter, So in the end, if there are no letters or only one letter in the HashSet, it means that it is a palindrome.

Code

Java

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Palindrome_Permutation {

    public class Solution {
        public boolean canPermutePalindrome(String s) {
            Map<Character, Integer> map = new HashMap<Character, Integer>();

            for(int i = 0; i < s.length(); i++){
                char c = s.charAt(i);
                map.put(c, 1 + map.getOrDefault(c, 0));
            }

            int count = 0;
            for (int each: map.values()) {
                if (each % 2 == 1) {
                    count++;
                }
            }

            return count < 2;
        }
    }

    public class Solution_set {
        public boolean canPermutePalindrome(String s) {

            Set<Character> hs = new HashSet<>();

            for (char each: s.toCharArray()) {
                if (hs.contains(each)) {
                    hs.remove(each);
                } else {
                    hs.add(each);
                }
            }

            return hs.size() <= 1;
        }
    }
}

// OJ: https://leetcode.com/problems/palindrome-permutation/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    bool canPermutePalindrome(string s) {
        int cnt[26] = {}, single = 0;
        for (char c : s) cnt[c - 'a']++;
        for (int n : cnt) {
            single += n % 2;
            if (single > 1) return false;
        }
        return true;
    }
};

class Solution(object):
    def canPermutePalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        oddChars = set()

        for c in s:
            if c in oddChars:
                oddChars.remove(c)
            else:
                oddChars.add(c)

        return len(oddChars) <= 1

266 - Palindrome Permutation

Question

Algorithm

Code

All Problems

All Solutions