Longest Palindrome

Условие

Дана строка s, состоящая из строчных и прописных букв. Нужно вернуть длину самого длинного палиндрома, который можно построить с использованием букв из этой строки. Регистр букв учитывается, то есть “Aa” нельзя использовать вместе как пару.

Примеры

Input: s = “abccccdd”

Output: 7

Explanation: Один из возможных палиндромов — “dccaccd”, длина которого равна 7.

Input: s = “a”

Output: 1

Explanation: Единственный возможный палиндром — сама буква “a”.

Решение

fun longestPalindrome(s: String): Int {
    val charCount = mutableMapOf<Char, Int>()
    
    // Подсчитываем количество каждой буквы
    for (char in s) {
        charCount[char] = charCount.getOrDefault(char, 0) + 1
    }

    var length = 0
    var hasOdd = false

    // Подсчитываем длину палиндрома
    for ((_, count) in charCount) {
        if (count % 2 == 0) {
            length += count  // Добавляем все четные количества
        } else {
            length += count - 1  // Добавляем четную часть нечетного количества
            hasOdd = true  // Отмечаем, что есть хотя бы одно нечетное количество
        }
    }

    // Если есть хотя бы одно нечетное количество, можем добавить одну центральную букву
    return if (hasOdd) length + 1 else length
}

Временная сложность

O(n), где n — длина строки s, так как мы проходим по строке для подсчета символов и затем обрабатываем их количество.

Пространственная сложность

O(1), так как количество уникальных символов ограничено (всего 52 возможных буквы).