最长回文串

题目

给定以个字符串，得出其重新排列后可组成最长的回文串长度。
回文串意思为， 不管从左到右读或从右到左读，均表现一致，比如单词level、noon，或中文的：上海自来水来自海上。

题目要求区分大小写：比如 Aba，不属于回文串。

示例

输入:
"abccccdd"
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

思路

• 如果某个字符x出现了偶数次，那么其出现的次数值一定是组成最终长度的一部分。
• 如果出现的是奇数次，那么x-1的值也是组成最终长度的一部分。
• 然后考虑特殊场景，当有字符出现奇数次时，其实是可以作为回文串的最中间部分存在的，但因为上一步中的x-1已经把这种场景全部减去掉了，所以需要找时机再加回来。

代码实现

1. 遍历字符串，得出每个字符出现的次数。
2. 新建变量res 存储回文串长度。
3. 如果出现次数t为偶数 那么 res+=t;
4. 如果出现次数为奇数 那么 res+=(t-1);
5. 最终结果如果小于字符串长度，那么一定是因为有字母出现过奇数次被减掉了，需要再加回来。但是，不管出现过多少个奇数次，最终也只可有一个用来作为回文串中心，所以如果res<length时，res+=1 即可；

class Solution {
    public int longestPalindrome(String s) {
        int[] cnt = new int[58]; //A~Z,a~z 共58个字符，所以建立长度58的数组用于统计每个字符出现的次数。
        for (char c : s.toCharArray()) {
                    cnt[c - 'A'] ++;
 // 此处的c - 'A' 其实是用字符c和字符‘A’的ACK2码作差，得到的结果即为某个字符在cnt数组中的下标，比如字符c值为‘A’，那么下标为0，值为‘B’那么下标为1，值为‘a’下标为26，以此类推......是很巧妙也是被广泛运用的一种统计字符的方法；
        }
        int res = 0;
        for (int t: cnt) {
            // 字符出现的次数最多用偶数次。
            if (t % 2 == 0){
                res += t;
            }else {
                res += t -1;
            }
        }
        if (res < s.length()){
              res += 1;
        }
        return  res; 
    }
}

复杂度

时间复杂度　Ｏ（２ｎ）可以近似为Ｏ（ｎ），空间复杂度中，因建立了个５８长度的数组，多了空间占用，但因为并不会随着字符串长度的增加而增加，占用量为常数级别，所以依然算作Ｏ（１）。