LeetCode 409. Longest Palindrome (Java版; Easy)

末蓝、 2023-07-17 02:47 17阅读 0赞

### [welcome to my blog][] ###

## LeetCode 409. Longest Palindrome (Java版; Easy) ##

#### 题目描述 ####

Given a string which consists of lowercase or uppercase letters, find the length of the longest 
    palindromes that can be built with those letters.
    
    This is case sensitive, for example "Aa" is not considered a palindrome here.
    
    Note:
    Assume the length of given string will not exceed 1,010.
    
    Example:
    
    Input:
    "abccccdd"
    
    Output:
    7
    
    Explanation:
    One longest palindrome that can be built is "dccaccd", whose length is 7.

#### 第一次做; 核心: 1)回文串中的字符要么出现偶数次, 要么出现奇数次, 而且最多有一个字符出现过奇数次, 所以统计s中各个字符出现的次数, 找出里面有多少对相同的字符, 再判断有没有出现过奇数次的字符, 见代码; 2) 为什么要统计有多少对相同的字符, 而不是直接使用字符的奇偶性? 看这个例子,ccc, 可以构成的回文串最长为3, 一对cc再加上一个c ####

class Solution { 
        public int longestPalindrome(String s) { 
            //input check
            if(s==null ||s.length()==0){ 
                return 0;
            }
            int n = s.length();
            //65:A 97:a
            int[] arr = new int[122-65+1];
            for(int i=0; i<n; i++){ 
                arr[s.charAt(i)-'A']++;
            }
            //even表示有多少对相同的元素; odd表示奇数个的元素出现过多少次
            int even=0, odd=0;
            for(int a : arr){ 
                even += a/2;
                if(a%2==1){ 
                    odd++;
                }
            }
            return odd>0? even*2+1 : even*2;
        }
    }

#### [力扣优秀题解][Link 1]; 统计字符串中出现次数为奇数的字符个数, 用count表示, 如果count==0, 表示所有的字符均出现偶数次, 所以最大的回文串就是整个字符串, 如果count>0, 那么最大的回文串长度就是原始字符串长度减去count再加1, 为什么要加1? 因为回文串中最多有一个字符出现奇数次 ####

public int longestPalindrome(String s) { 
        // 找出可以构成最长回文串的长度
        int[] arr = new int[128];
        for(char c : s.toCharArray()) { 
            arr[c]++;
        }
        int count = 0;
        for (int i : arr) { 
            count += (i % 2);
        }
        return count == 0 ? s.length() : (s.length() - count + 1);

[welcome to my blog]: https://littlehaes.com
[Link 1]: https://leetcode-cn.com/problems/longest-palindrome/solution/zui-chang-hui-wen-chuan-by-leetcode-solution/