Перейти к содержанию

Longest Palindrome

🇷🇺 Название: Самый длинный палиндром
LeetCode: longest-palindrome
Временная сложность: O(n)
Пространственная сложность: O(1)

Решение

from collections import Counter  


class Solution:  
    def longestPalindrome(self, s: str) -> int:  
        values = Counter(s).values()  
        result = 0  
        has_odd = False  

        for value in values:  
            if value % 2 == 0:  
                result += value  
            else:  
                result += value - 1  
                has_odd = True  

        if has_odd:  
            return result + 1  

        return result

🇺🇸 Условие

Given a string s which 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.

🇷🇺 Условие

Примеры

Example 1:

Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:

Input: s = "a"
Output: 1
Explanation: The longest palindrome that can be built is "a", whose length is 1.

{
  "examples": [
    {
      "input": {
        "s": "abccccdd"
      },
      "output": 7
    },
    {
      "input": {
        "s": "a"
      },
      "output": 1
    }
  ]
}

Ограничения

  • \(1 \leq s.length \leq 2000\)
  • s consists of lowercase and/or uppercase English letters only.

Потребление ресурсов

⏱ Time complexity: O(n)

  • Counter(s) — один проход по строке s длины n.
  • Проход по значениям счётчика — максимум количество уникальных символов, обычно значительно меньше n.
  • Итог: линейное время O(n).

Итог: O(n)

🧠 Space complexity: O(1)

  • Counter хранит количество уникальных символов.
  • При фиксированном наборе символов (например, латиница) — память константна.
  • Иначе — O(k), где k — число уникальных символов.

Итог: O(1) при фиксированном алфавите

easy hash-table string greedy


Metadata

  • title_rus: Самый длинный палиндром
  • difficulty: Easy
  • leetcode_url: https://leetcode.com/problems/longest-palindrome/
  • topics: ['Hash Table', 'String', 'Greedy']
  • time: O(n)
  • space: O(1)
  • grind75: True
  • tags: ['Easy', 'Greedy', 'Hash Table', 'String', 'problem']
  • git_revision_date_localized: 5 июля 2025 г.
  • git_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
  • git_revision_date_localized_tag:
  • git_revision_date_localized_raw_date: 5 июля 2025 г.
  • git_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
  • git_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
  • git_revision_date_localized_raw_iso_date: 2025-07-05
  • git_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
  • git_revision_date_localized_raw_timeago:
  • git_revision_date_localized_raw_custom: 05. июля 2025
  • git_site_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
  • git_site_revision_date_localized_tag:
  • git_site_revision_date_localized: 5 июля 2025 г.
  • git_site_revision_date_localized_raw_date: 5 июля 2025 г.
  • git_site_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
  • git_site_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
  • git_site_revision_date_localized_raw_iso_date: 2025-07-05
  • git_site_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
  • git_site_revision_date_localized_raw_timeago:
  • git_site_revision_date_localized_raw_custom: 05. июля 2025