409. Longest Palindrome – Leetcode Solutions

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.

class Solution:
    def longestPalindrome(self, s: str) -> int:
        # Count the frequency of each character
        char_count = Counter(s)
        
        # Initialize the length of the longest palindrome
        palindrome_length = 0
        odd_found = False
        
        # Iterate over the character frequencies
        for count in char_count.values():
            if count % 2 == 0:
                # Add even counts directly
                palindrome_length += count
            else:
                # Add the largest even part of the odd count
                palindrome_length += count - 1
                # Flag that an odd count was found
                odd_found = True
        
        # If any odd counts were found, one character can be added to the center
        if odd_found:
            palindrome_length += 1
        
        return palindrome_length

class Solution {
public:
    int longestPalindrome(string s) {
        // Create a hash map to count the frequency of each character in the string
        unordered_map<char, int> charCount;

        // Populate the frequency map
        for (char c : s) {
            charCount[c]++;
        }

        // Initialize variables to store the length of the longest palindrome
        int palindromeLength = 0;
        bool oddFound = false;

        // Iterate over the frequency map
        for (auto pair : charCount) {
            int freq = pair.second;
            
            // If the frequency is even, add it fully to the palindrome length
            if (freq % 2 == 0) {
                palindromeLength += freq;
            } else {
                // If the frequency is odd, add the largest even part (freq - 1)
                palindromeLength += freq - 1;
                // Mark that at least one odd frequency exists
                oddFound = true;
            }
        }

        // If there was any odd frequency, we can place one odd character in the center of the palindrome
        if (oddFound) {
            palindromeLength += 1;
        }

        // Return the computed length of the longest palindrome
        return palindromeLength;
    }
};

var longestPalindrome = function(s) {
    // Create a map to count the occurrences of each character
    const charCount = new Map();
    
    // Loop through the string and count the frequency of each character
    for (const char of s) {
        charCount.set(char, (charCount.get(char) || 0) + 1);
    }
    
    // Initialize variables to calculate the palindrome length
    let palindromeLength = 0;
    let hasOddFrequency = false; // Flag to track if we have at least one odd frequency
    
    // Iterate over the character frequencies
    for (const count of charCount.values()) {
        // Add the largest even number of characters to the palindrome length
        palindromeLength += Math.floor(count / 2) * 2;
        
        // If the count is odd and we don't yet have an odd character, set the flag
        if (count % 2 !== 0) {
            hasOddFrequency = true;
        }
    }
    
    // If there is at least one character with an odd count, we can place it in the center
    if (hasOddFrequency) {
        palindromeLength += 1;
    }
    
    // Return the calculated palindrome length
    return palindromeLength;
};

class Solution {
    public int longestPalindrome(String s) {
        // Step 1: Create a frequency map to count the occurrences of each character
        int[] charCounts = new int[128]; // Assuming ASCII characters (128 possible characters)
        
        // Count the occurrences of each character in the string
        for (char c : s.toCharArray()) {
            charCounts[c]++;
        }
        
        // Step 2: Calculate the longest palindrome length
        int palindromeLength = 0;
        boolean oddCountFound = false; // To track if there is any character with an odd frequency
        
        // Iterate over the frequency array
        for (int count : charCounts) {
            // If the count is even, add it to the palindrome length
            if (count % 2 == 0) {
                palindromeLength += count;
            } else {
                // If the count is odd, add the largest even part (count - 1) to the palindrome length
                palindromeLength += count - 1;
                oddCountFound = true; // Mark that we found at least one odd frequency
            }
        }
        
        // Step 3: If there is at least one character with an odd count,
        // we can use one of those characters as the center of the palindrome
        if (oddCountFound) {
            palindromeLength++;
        }
        
        // Step 4: Return the calculated palindrome length
        return palindromeLength;
    }
}