Skip to content

266. Palindrome Permutation 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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