> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/hash/tong-ji-pin-lv/palindrome-permutation.md).

# 266. Palindrome Permutation

https\://leetcode.com/problems/palindrome-permutation/description/

> Given a string, determine if a permutation of the string could form a palindrome.
>
> For example,
>
> "code" -> False, "aab" -> True, "carerac" -> True.

## Thoughts

检验给定字符串能否通过重组变成回文。构成palindrome有且只有一个字符出现奇数次。统计奇偶用0/1记录就可以，出现奇数次1，偶数次置回0，利用次思想可以用位操作或hash set实现。

## Code

```java
class Solution {
public:
    bool canPermutePalindrome(string s) {
        vector<int> freqs(128, 0);
        for (const auto c : s) {
            freqs[c] = !freqs[c];
        }
        
        for (int i = 0, cnt = 0; i < 128; ++i) {
            if (freqs[i] != 0) {
                if (cnt > 0) return false;
                ++cnt;
            }
        }

        return true;
    }
};
```

```java
class Solution {
    public boolean canPermutePalindrome(String s) {
        Set<Character> visited = new HashSet<>();
        for (char c : s.toCharArray()) {
            if (visited.contains(c)) {
                visited.remove(c);
            } else {
                visited.add(c);
            }
        }

        return visited.size() <= 1;
    }
}
```

## Analysis

时间复杂度O(N).