Longest Palindrome easy

Problem Statement

Given a string s which consists of lowercase or uppercase letters, find 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 here.

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 built is "a", whose length is 1.

Steps

1. Character Counting: Create a map (or object in JavaScript/TypeScript) to store the frequency of each character in the input string s.
2. Odd and Even Counts: Iterate through the character frequencies. Keep track of the count of characters with odd frequencies and the total length.
3. Constructing the Palindrome: The maximum length of a palindrome is the total length of characters with even frequencies, plus 1 if there's at least one character with an odd frequency (this odd character will be the middle of the palindrome).

Explanation

The key idea is that a palindrome can be built using characters with even frequencies. We can pair up these characters to form the palindrome's symmetric structure. If there's a character with an odd frequency, it can be placed in the middle of the palindrome, and the remaining characters are paired as before.

Code (TypeScript)

function longestPalindrome(s: string): number {
    const charCounts: { [char: string]: number } = {};
    for (const char of s) {
        charCounts[char] = (charCounts[char] || 0) + 1;
    }

    let oddCount = 0;
    let totalLength = 0;
    for (const count of Object.values(charCounts)) {
        if (count % 2 === 0) {
            totalLength += count;
        } else {
            oddCount++;
            totalLength += count - 1; // Use all but one of odd count characters
        }
    }

    return oddCount > 0 ? totalLength + 1 : totalLength; //Add 1 if there's an odd-count character to use as center.
}

Complexity

• Time Complexity: O(n), where n is the length of the string s. This is because we iterate through the string once to count character frequencies and then iterate through the frequencies (which is at most the size of the alphabet).
• Space Complexity: O(k), where k is the number of unique characters in the string s. In the worst case, k could be n (if all characters are unique), but it's often much smaller. This is the space used to store the character counts.