Sobes.tech
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:

  1. Count the number of each character.
  2. 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).
  3. 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;
}