SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem asks for the length of the longest palindrome that can be built using characters from the input string s. A palindrome is a string that reads the same backward as forward. We are allowed to rearrange the characters of s to form the longest possible palindrome. The task is to return the length of that palindrome.

Intuition

To form a palindrome, characters need to appear an even number of times to ensure symmetry. For instance, the character "a" can appear twice and still be placed in both the left and right halves of the palindrome. If a character appears an odd number of times, one instance can still be placed in the center of the palindrome. Therefore, the idea is to count how many characters can form pairs and if any odd-frequency character can be placed in the middle.

Approach

1. Character Frequency Count: Traverse the string and count the frequency of each character.
2. Calculate Longest Palindrome Length:
   • For each character, if it appears an even number of times, all instances can contribute to the palindrome.
   • If a character appears an odd number of times, one fewer than its count (i.e., the largest even number) can contribute to the palindrome, and one instance can potentially be placed in the center.
3. Return Result: Return the total length of the palindrome, adding 1 if any odd-frequency characters exist, as one can be placed in the middle.

Complexity

Time Complexity:

O(n), where n is the length of the string s. We traverse the string once to build the frequency map and then iterate through the map to compute the length of the palindrome.

Space Complexity:

O(1) or O(c), where c is the number of unique characters. Since the character set is limited (e.g., 26 for lowercase English letters), the space complexity is considered constant.

Code

C++

class Solution {
public:
    int longestPalindrome(string s) {
        if (s.length() < 2)
            return s.length();
        unordered_map<char, int> map;
        int longest = 0;
        for (char c : s) {
            map[c]++;
            if (map[c] % 2 == 0)
                longest += 2;
        }
        if (s.length() > longest)
            longest += 1;
        return longest;
    }
};

Python

class Solution:
    def longestPalindrome(self, s: str) -> int:
        if len(s) < 2:
            return len(s)
        
        char_count = {}
        longest = 0
        for char in s:
            char_count[char] = char_count.get(char, 0) + 1
            if char_count[char] % 2 == 0:
                longest += 2
        
        if len(s) > longest:
            longest += 1
        
        return longest

Java

class Solution {
    public int longestPalindrome(String s) {
        if (s.length() < 2) return s.length();
        HashMap<Character, Integer> map = new HashMap<>();
        int longest = 0;
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
            if (map.get(c) % 2 == 0) longest += 2;
        }
        if (s.length() > longest) longest += 1;
        return longest;
    }
}

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function (s) {
    if (s.length < 2) return s.length;
    const map = {};
    let longest = 0;
    for (let i = 0; i < s.length; i++) {
        map[s[i]] = (map[s[i]] || 0) + 1;
        if (map[s[i]] % 2 === 0) longest += 2;
    }
    if (s.length > longest) longest += 1;
    return longest;
};