Senior
For a given string, it is necessary to determine the length of the largest palindrome that can be formed from its characters. A palindrome is a word that reads the same from the beginning and the end, for example "level" or "deified". Example: Input: aaabbbcccddd Output: 11 (palindrome dccbbaaabbccd)
sobes.tech AI
Answer from AI
To find the length of the longest palindrome that can be formed from the characters of a string, you need to consider that a palindrome is symmetric, and there can be only one character with an odd frequency in the center.
Algorithm:
- Count the number of each character.
- For each character, add the maximum even number of its occurrences to the palindrome length (for example, if a character appears 5 times, add 4).
- If there is at least one character with an odd count, add 1 (the central character).
Example in Java:
public int longestPalindromeLength(String s) {
int[] counts = new int[128]; // for ASCII
for (char c : s.toCharArray()) {
counts[c]++;
}
int length = 0;
boolean oddFound = false;
for (int count : counts) {
length += (count / 2) * 2; // add even count
if (count % 2 == 1) {
oddFound = true;
}
}
if (oddFound) {
length += 1; // central character
}
return length;
}