Для заданной строки необходимо определить длину самого большого палиндрома, который можно составить из ее символов.

Условие

Для заданной строки необходимо определить длину самого большого палиндрома, который можно составить из ее символов.

Палиндром — это слово, которое одинаково читается с начала и с конца, например "шалаш" или "потоп".

Пример: Input: aaabbbcccddd Output: 11 (палиндром dccbbaaabbccd)

Ответ

Чтобы найти длину самого большого палиндрома, который можно составить из символов строки, нужно учитывать, что палиндром симметричен, и в центре может быть только один символ с нечетной частотой.

Алгоритм:

1. Подсчитать количество каждого символа.
2. Для каждого символа добавить в длину палиндрома максимально четное количество его вхождений (например, если символ встречается 5 раз, добавить 4).
3. Если есть хотя бы один символ с нечетным количеством, добавить 1 (центральный символ).

Пример на Java:

public int longestPalindromeLength(String s) {
    int[] counts = new int[128]; // для ASCII
    for (char c : s.toCharArray()) {
        counts[c]++;
    }
    int length = 0;
    boolean oddFound = false;
    for (int count : counts) {
        length += (count / 2) * 2; // добавляем четное количество
        if (count % 2 == 1) {
            oddFound = true;
        }
    }
    if (oddFound) {
        length += 1; // центральный символ
    }
    return length;
}