java - 找到最长的回文，代码通过了一半的测试用例

Question

给定一个 String s，我试图找到可能的最长回文。问题指定它区分大小写，因此 'A' != 'a'。我下面的尝试通过了 49/95 的 Leetcode 测试用例，但我不确定我哪里出错了......

public class Solution {
    public int longestPalindrome(String s) {
        if (s.equals("")) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        int total = 0;
        int greatestOdd = 0;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            int value = entry.getValue();
            if (value % 2 == 0) {
                total += value;
            } else {
                if (value > greatestOdd) {
                    greatestOdd = value;
                }
            }
        }
        total += greatestOdd;
        return total;

    }
}

其思想是，回文由计数为偶数的字符和一个计数为奇数的字符(或者可能为 0 个计数为奇数的字符)组成。所以我跟踪 HashMap 中的所有字符计数。

然后我循环遍历 HashMap 中的所有值，如果它们是偶数，则添加到总计中。我还跟踪最大奇数(初始化为 0，以防没有奇数计数的字母)。

我认为这是正确的想法，但有些地方不对......

练习链接:https://leetcode.com/problems/longest-palindrome/?tab=Description

Answer 1

您的逻辑是正确的，但是一旦您计算出最大奇数值，您应该将其从 map 中删除并考虑所有其他字符出现奇数次。

您应该通过减去 1 并将其添加到您的回文长度来使它们均匀:

我的代码:

public int longestPalindrome(String s) {
    HashMap<Character,Integer> map = new HashMap<>();
    for (Character c : s.toCharArray()) {
        if(map.containsKey(c)) {
            map.put(c,map.get(c)+1);
        } else {
            map.put(c,1);
        }
    }
    int maxOdd = 0;
    char maxOddChar = Character.MIN_VALUE;
    int palindromeLength = 0;
    for (Character c : map.keySet()) {
        if(map.get(c)%2==0) {
            palindromeLength += map.get(c);
        } else {
            if(maxOdd<map.get(c)) {
                maxOdd = map.get(c);
                maxOddChar = c;
            }
        }
    }
    palindromeLength += maxOdd;
    map.remove(maxOddChar);
    //Considering other odd characters as well  
    for (Character c : map.keySet()) {
        if(map.get(c)%2!=0) {
            palindromeLength += map.get(c)-1;
        }
    }
    return palindromeLength;
}

Example: aabbbcccccdd

Hashmap ->  a->2,b->3,c->5,d->2
Greatest odd value = c->5
Total palindrome length : a+d+c = 2+2+5 = 9

// But you are missing b->3 can also be added 
// in the palindrome, but using only 2 b's and neglecting 1

Total palindrome length : 9+2 = 11