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:
1
2
3
4
5
6
7
8
|
Input:
"abccccdd"
Output:
7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.
|
- 用两个数组保存大写和小写的每个字母的count
- 遍历所有字母的count，如果count是偶数，那就可以放在目标回文的两边，如果是奇数，可以取两个放在目标回文的两边。所以先ans += count/2， 返回ans*2
- 要注意的是，如果存在奇数个的count，比如说1个，那么可以把他放到目标回文中间，那么ans += 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class {
public int longestPalindrome(String s) {
int[] lowercast = new int[26];
int[] uppercast = new int[26];
int count = 0;
int sole = 0;
for (int i=0; i<s.length(); i++) {
char c = s.charAt(i);
if (c >= 'a' && c<='z') {
lowercast[c-'a'] ++;
}
if (c >='A' && c<='Z') {
uppercast[c-'A'] ++;
}
}
for (int i=0; i<26; i++) {
count += lowercast[i]/2;
count += uppercast[i]/2;
if (uppercast[i]%2 == 1 || lowercast[i]%2 == 1) {
sole = 1;
}
}
return count*2 + sole;
}
}
|
近期评论