409.最长回文串

409. 最长回文串

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。
在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

/**
 思路：
 遍历字符数组 一个字符每出现2次就重置其出现次数 同时让最长回文串长度 +2
 遍历字符次数数组 发现一个出现一次的就停止遍历 并让最长回文串长度 +1 ，此时就得到了最终最长回文子串的长度
 */
class Solution {
    public int longestPalindrome(String s) {
        
        //0.定义需要的数据结构
        int[] charNums = new int[128];
        char[] charArray = s.toCharArray();
        int length=0;

        for (char c : charArray) {
            //字符出现就++
            charNums[c]++;
            if (charNums[c] == 2) {//一个字符出现2次了 重置为0
                charNums[c] = 0;
                length += 2; //最大长度加2
            }
        }
        
        for (int charNum : charNums) {
            //有一个字符出现了一次 对构成回文串的长度加一 并退出  aacbb
            if(charNum==1){
                length++;
                break;
            }
        }
        return length;
    }
}

/**
 思路：天天爱消除
 回文是成对出现的 利用结合去重，最后剩下的就是出现次数为奇数的字符
 */
class Solution1 {
    public int longestPalindrome(String s) {

        Set<Character> set = new HashSet<>();
        //1.消除出现次数是偶数的字符
        for (int i = 0; i < s.length(); i++) {
            if (!set.remove(s.charAt(i))) {
                set.add(s.charAt(i));
            }
        }
    
        /**
        2.
        集合为空就表示整个字符串是回文串 
        不为空就减去集合元素个数加上一, 加一是因为添加一个字符放在最中间依然是回文串
        */
        return set.isEmpty() ? s.length() : s.length() - set.size() + 1;

    }
}