LeetCode 409 - Longest Palindrome

原题链接：409. Longest Palindrome

题目

给定一个字符串（只包含大小写字母），求该字符串能够组成的最长回文长度。大小写敏感。假设给定字符串长度不超过 1010 。

举例：
“abccccdd”

返回：
7

解释：
最长回文为 “dccaccd”

思路

字符排序后数数，先算出所有双数字母总长度，如果存在单数字母，则长度加 1 ，否则直接返回。
时间复杂度 $O(n)$ ，空间复杂度 $O(n)$

代码：

public class Solution {
    public int longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] charArray = s.toCharArray();
        // 自然排序
        Arrays.sort(charArray);
        int length = charArray.length;
        char current = charArray[0];
        int count = 1;
        for (int i = 1; i < charArray.length; i++) {
            if (charArray[i] == current) {
                count++;
            } else {
                if (count % 2 == 1) {
                    length--;
                }
                current = charArray[i];
                count = 1;
            }
        }
        if (count % 2 == 0) {
            // 如果都是双数，则回文长度必然与原字符长度相等，否则必有一个单数的字母。
            if (length < charArray.length) {
                return length + 1;
            }
        }
        return length;
    }
}

题目
思路

LeetCode 409 - Longest Palindrome

题目

思路

FEATURED TAGS

FRIENDS