Leetcode 409. Longest Palindrome

Description

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

Example 1:

Input: s = "abccccdd"
Output: 7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:

Input: s = "a"
Output: 1

Example 3:

Input: s = "bb"
Output: 2

Constraints:

  • 1 <= s.length <= 2000
  • s consits of lower-case and/or upper-case English letters only.

Solution

求字符串能组成的最长回文字符串长度,将所有的偶数次字符加上可能有的一次奇数次字符出现次数就行。

class Solution {
    public int longestPalindrome(String s) {
        int n = s.length();
        int[] counts = new int[128];
        int res = 0;
        for (char c : s.toCharArray()) {
            counts[c]++;
        }
        boolean flag = false;
        for (int count : counts) {
            res += count / 2 * 2;
            if ((count & 1) == 1)
                flag = true;
        }
        return flag ? res + 1 : res;
    }
}

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号