I've been working on this problem:
"Given a string
swhich 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.
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.
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.
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:
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