HASHP02 - Editorial

editorial
1

Problem Link - Length of Longest Palindrome in Hashing

Problem:

Given a string S which consists of lowercase Latin letters, return the length of the longest palindrome that can be built with those letters.

Approach:

  1. Understand Palindrome Properties: A palindrome reads the same forwards and backward. In a palindrome, characters must appear in pairs, except for one character that can appear in the center.

  2. Count Character Frequencies: Use a hash map (or unordered map) to count the occurrences of each character in the string.

  3. Calculate Maximum Palindrome Length:

  • Keep track of the total length of the palindrome.
  • Check if there’s at least one character with an odd count.
  • For each character count:
    • If the count is even, add it directly to the total length.
    • If the count is odd, add the largest even part of it (i.e., count - 1) to the total length and mark that an odd count has been found.
  1. Handle Center Character: If there is at least one character with an odd frequency, add 1 to the total length to account for the center character of the palindrome.

Complexity:

  • Time Complexity: O(N), where N is the length of the string (for counting characters).
  • Space Complexity: O(1), as the maximum number of unique characters is constant (26 lowercase letters).