Trying to find the longest palindrome for this input

Question

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:

Input: "abccccdd"

Output: 7

Explanation:

One longest palindrome that can be built is "dccaccd", whose length is 7.

My code works for simple inputs such as "abccccdd" and "banana" but fails for "civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth". I'm not sure how to debug it.

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        char[] carr = s.toCharArray();
        Arrays.sort(carr);
        int leftInd = 0;
        int rightInd = 0;
        for(int i=0; i<carr.length; i++){
            if(map.containsKey(carr[i]))
                continue;
            else
                map.put(carr[i], 1);
        }
        for(int i=0; i<carr.length-1; i++){
            for(int j=i+1; j<carr.length; j++){
                if(carr[i]==carr[j]){
                    if(map.get(carr[i])==null)
                        continue;
                    carr[j] = Character.MIN_VALUE;
                    int count = map.get(carr[i]);
                    map.put(carr[i], count + 1);
                }
            }
        }
        int ans = 0;
        int[] oddValArr = new int[map.size()];
        int oddInd = 0;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            Character key = entry.getKey();
            Integer value = entry.getValue();
            if(value % 2 == 0){
                ans += value;
            }
            else{
                oddValArr[oddInd] = value;
                oddInd++;
            }
        }
        int biggestOddNum = 0;
        for(int i=0; i<oddValArr.length; i++){
            if(oddValArr[i] > biggestOddNum)
                biggestOddNum = oddValArr[i];
        }
        return ans + biggestOddNum;
     }
}

Output 655

Expected 983

Answer 1

Your mistake here, is that you use only the biggest odd group out of your oddValArr. For example, if the input is "aaabbb", the biggest palindrome is "abbba", so group a had length 3, which is an odd number, and we used 3 - 1 = 2 letters of it.

Also, those nested for loops can be replaced with one for, using Map:

public int longestPalindrome(String s) {
    Map<Character, Integer> map = new HashMap<>();  // letter groups
    for(int i=0; i<s.length(); i++){
        char c = s.charAt(i));
        if(map.containsKey(c))
            map.put(c, map.get(i) + 1);
        else
            map.put(c, 1);
    }

    boolean containsOddGroups = false;
    int ans = 0;
    for(int count : map.values()){
        if(count % 2 == 0)  // even group
            ans += count;
        else{  // odd group
            containsOddGroups = true;
            ans += count - 1;
        }
    }
    if(!containOddGroups)
        return ans;
    else
        return ans + 1;  // we can place one letter in the center of palindrome
}