Longest palindrome length algorithm finding incorrect length for long strings

Question

I've been working on this problem:

"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."

When trying to come up with a solution to this problem before writing any code down my though process was construct a string that follows the trend of having the least even frequency of characters first then moving up in significance where in the middle you have the largest odd frequency of characters and then count its length.
This changed though, as I realised I only needed to return the length so I then thought to only count the even occurrences and add it to the greatest odd frequency, which should return the longest palindrome length.

The Java code I tried to achieve this is:

    public static int longestPalindrome(String s) {
        //variables
        int length = 0;
        int greatestOddFreaquency = 0;
        TreeMap<Character, Integer> tm = new TreeMap<Character, Integer>();

        //lenght 1
        if (s.length() == 1) {
            return 1;
        }

        for (int i = 0; i < s.length(); i++) {
            int total = 0; //to count how many times a charcter occurs

            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    total++;
                }
            }


            if (total % 2 != 0 && total >= greatestOddFreaquency) {
                greatestOddFreaquency = total;
            } else if (total % 2 == 0) {
                tm.put(s.charAt(i), total);
            }
        }

        for (Map.Entry<Character,Integer> entry : tm.entrySet()) {
            length += entry.getValue();
            //System.out.println("Key " + entry.getKey() + " val " +entry.getValue());

        }

        return length+=greatestOddFreaquency;
    }

However, when running this on an extremely long string my code fails. Any help would be greatly appreciated :)

To clarify for the flags raised: An example of an input is "abccccdd" which would result in an output of 7, which is something my code achieves. As for an input which causes my code to fail:

"civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"

This input causes my code to output 655 but the expected output is 983.

Finally when trying to come up with a solution to this problem I had the initial idea that if I maximise the odd frequency then the length of the final palindrome would also be maximised.

I should also mention that I have been testing my code against the given test cases that this problem comes with.

Answer 1

I think your issue is not programming, but understanding the question. You need to analyze the question first, to find the formal answer, that you then can implement.

Formal analysis

In the absence of dictionary, all words are valid. So aAa is valid, and so is acceptable. Therefore we can disregard word validity.

An acceptable palindrome "p" in that case, based on a parameter "seed", is ANY sequence of characters "s", followed by an optional center character "c", followed by reversing s : p := s+c+reverse(s) ; with the condition that each character in p has lower or same occurrence than in the given seed.

Since a character in s will appear twice as much in p, that means the occurrence of this character in s is at most half its occurrence in seed

So the length of s (the string that is mirrored) is maxed when each character of seed appear half its occurrence (rounded down : integer division) in s ; if there are no odd-occurrence of character in seed, then the middle character c is empty (it's better to put it in s so it appears also in reverse(s))

So the answer is : the longest palindrome's length is the sum of the occurrences of the chars in seed, rounded each down to even (so a char appearing 5 times counts as 4 ) ; plus one if there is a char with an odd occurrence in seed.

Implementation

The first step would be, to count all the characters of seed. We don't care which char has which occurrence, we just want the occurrences :

        List<Integer> allOccurences = 
// chars() gets the IntStream of chars in seed,
// boxed() makes it a Stream<Integer> so we have more utilities
            seed.chars().boxed()
// we group each integer by itself,
// so we have the list of integer occurence per integer appearing
            .collect(Collectors.groupingBy(i->i))
// we just want the size of those lists, which is the occurences      
            .values().stream().map(List::size).toList();

The next step is to count the occurrences that can be part of the mirrored string (s), as well as detect if an occurrence is odd :

        boolean hasOdd=false;
        int mirroredSize = 0;
        for(int occurrence : allOccurences) {
            hasOdd|= (occurrence%2==1);
            mirroredSize+= (occurrence/2);
        }

Then return the deduced size :

        return (hasOdd?1:0)+2*mirroredSize;

edit:

Test

import java.util.List;
import java.util.stream.Collectors;

public class MaxPaliTest {

    public static void main(String[] args) {
        printMaxPali(
                "civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth");

    }

    public static void printMaxPali(String seed) {
        System.err.println("max pali is " + maxPali(seed) + " for (size=" + seed.length() + ") " + seed);
    }

    public static int maxPali(String seed) {
        List<Integer> allOccurences = seed.chars().boxed()
                .collect(Collectors.groupingBy(i -> i))
                .values().stream().map(List::size).toList();
        boolean hasOdd = false;
        int mirroredSize = 0;
        for (int occurrence : allOccurences) {
            hasOdd |= occurrence % 2 == 1;
            mirroredSize += occurrence / 2;
        }
        return (hasOdd ? 1 : 0) + 2 * mirroredSize;
    }

}

max pali is 983 for (size=999) civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth

Answer 2

If we want to avoid using Stream...

Let's first describe a palindrome from the point of view of this exercise:

A palindrome is a word that contains "0" or "1" letter repeated an odd number of times, and "0" or more letters repeated an even number of times.

In short, there can only be one letter repeated an odd number of times.

This makes the analysis trivial, each letter that is repeated as "even" will increase the output by its number of occurrences, something like:

int amount = amountOfLetters( letter );  // 4
if( amount % 2 == 0 ) palindromeSize += amount; 

Now if the value of amount is odd, we know that we can only add all the elements once, so we will use a boolean, which tells us when this has happened.

booleano find = true;
int amount = amountOfLetters( letter );  // 5
else{

      // If we have not previously added an odd amount, we do so
    if( find ) palindromeSize += amount; 

      // By removing one we make the number of appearances even
    else palindromeSize += amount - 1;

We put everything together...

int count( String letters ) {        
    Map<Character, Integer> map = new HashMap<>();
    
       // We count the appearances of each letter
    for( int i = 0; i< letters.length(); i++ ) {
        Character cha = letters.charAt( i );
        Integer amount = map.get( cha );
        if( amount == null ) map.put( cha, 1 );
        else map.put( cha, map.get( cha ) + 1 );
    }
    
    boolean findOdd = true; 
    int output = 0;
    
    for( Character cha : map.keySet() ) {            
        int aux = map.get( cha );
        if(  aux % 2 == 0 ) output += aux;
        else if( findOdd  ) {
            findOdd = false;
            output+= aux;
        }
        else {
            output += aux - 1;
        }
    }
    return output;        
}