Leetcode

Palindrome Permutation

  • Time:O(n)
  • Space:O(n)

C++

class Solution {
 public:
  bool canPermutePalindrome(string s) {
    unordered_set<char> seen;

    for (const char c : s)
      if (!seen.insert(c).second)
        seen.erase(c);

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

JAVA

class Solution {
  public boolean canPermutePalindrome(String s) {
    Set<Character> seen = new HashSet<>();

    for (final char c : s.toCharArray())
      if (!seen.add(c))
        seen.remove(c);

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

Python

class Solution:
  def canPermutePalindrome(self, s: str) -> bool:
    seen = set()

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

    return len(seen) <= 1