LeetCode 409 - Longest Palindrome

作者 QIFAN 日期 2016-12-26
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;
}
}