Palindrome

1. longest palindrome substring
2. valid palindrome
3. palindrome permutation
4. palindrome permutation II
5. Valid Palindrome II

//todo

https://leetcode.com/problems/shortest-palindrome/description/

1. Longest Palindrome Substring

two pointers + middle out

需要注意两个pointer的position。最后的长度是right - left - 1，-1是因为当while loop结束的时候，left, right实际上被forward多了一步，指的是不对称的部分。

注意：当Middle out的时候，因为不确定palindrome is odd num of length or even, 先用两个while loop把和i相同的元素都算进来，因为'aaa' & 'aa' 都可以组成有效的palindrome。

4. Palindrome Permutation II

dfs + check occurrence of letters

第一步，数每个字母的个数。

第二步，判断 str 可不可以组成palindrome。如果只有一个letter的出现次数是单数的话，可以。如果超过1个letter是单数的话，那么就肯定无法组成palindorme了。可以直接return new list。

在检查的时候，顺便把occurence / 2。这样子，在dfs组成有效的palindrome的时候，就只需要组成一半的string了。

第三步，如果有单数的字母的话，那么，那个字母必须得是center letter。要不然的话，从empty string开始。接下来就是dfs，往string上加字母了。