Longest Palindrome

                                            
class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> freq;
        int length = 0;
        bool hasOdd = false;
        
        for(char c : s) {
            freq[c]++;
        }
        
        for(auto& p : freq) {
            if(p.second % 2 == 0) {
                length += p.second;
            } else {
                length += p.second - 1;
                hasOdd = true;
            }
        }
        
        return hasOdd ? length + 1 : length;
    }
};

                                            
class Solution {
    public int longestPalindrome(String s) {
        int[] count = new int[128];
        for (char c : s.toCharArray()) {
            count[c]++;
        }
        
        int palindromeLength = 0;
        boolean hasOdd = false;
        
        for (int num : count) {
            palindromeLength += num / 2 * 2;
            if (num % 2 == 1) {
                hasOdd = true;
            }
        }
        
        return hasOdd ? palindromeLength + 1 : palindromeLength;
    }
}

                                            
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        char_count = {}
        palindrome_length = 0
        odd_found = False
        
        for char in s:
            if char in char_count:
                char_count[char] += 1
            else:
                char_count[char] = 1
        
        for count in char_count.values():
            if count % 2 == 0:
                palindrome_length += count
            else:
                palindrome_length += count - 1
                odd_found = True
        
        return palindrome_length + 1 if odd_found else palindrome_length

                                            
int longestPalindrome(char* s) {
    int count[128] = {0};
    int length = 0;
    int oddFound = 0;
    
    while (*s) {
        count[*s]++;
        s++;
    }
    
    for (int i = 0; i < 128; i++) {
        length += count[i] / 2 * 2;
        if (count[i] % 2 == 1) {
            oddFound = 1;
        }
    }
    
    return length + oddFound;
}

                                            
public class Solution {
    public int LongestPalindrome(string s) {
        Dictionary<char, int> dict = new Dictionary<char, int>();
        int result = 0;
        
        foreach(char c in s){
            if(dict.ContainsKey(c)){
                dict[c]++;
            } else {
                dict[c] = 1;
            }
        }
        
        bool hasOdd = false;
        
        foreach(var pair in dict){
            if(pair.Value % 2 == 0){
                result += pair.Value;
            } else {
                result += pair.Value - 1;
                hasOdd = true;
            }
        }
        
        return hasOdd ? result + 1 : result;
    }
}

                                            
/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function(s) {
    let charCount = {};
    let maxLength = 0;
    let hasOdd = false;
    
    for(let char of s) {
        if(charCount[char] === undefined) {
            charCount[char] = 1;
        } else {
            charCount[char]++;
        }
    }
    
    for(let char in charCount) {
        if(charCount[char] % 2 === 0) {
            maxLength += charCount[char];
        } else {
            maxLength += charCount[char] - 1;
            hasOdd = true;
        }
    }
    
    return hasOdd ? maxLength + 1 : maxLength;
};

                                            
function longestPalindrome(s: string): number {
    const charCount = new Map<string, number>();
    
    for (let char of s) {
        charCount.set(char, (charCount.get(char) || 0) + 1);
    }
    
    let palindromeLength = 0;
    let hasOddCount = false;
    
    for (let count of charCount.values()) {
        palindromeLength += Math.floor(count / 2) * 2;
        
        if (count % 2 !== 0) {
            hasOddCount = true;
        }
    }
    
    return hasOddCount ? palindromeLength + 1 : palindromeLength;
};

                                            
class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function longestPalindrome($s) {
        $charCount = [];
        $length = 0;
        
        for ($i = 0; $i < strlen($s); $i++) {
            $char = $s[$i];
            if (isset($charCount[$char])) {
                $charCount[$char]++;
            } else {
                $charCount[$char] = 1;
            }
        }
        
        $oddFound = false;
        
        foreach ($charCount as $count) {
            if ($count % 2 == 0) {
                $length += $count;
            } else {
                $length += $count - 1;
                $oddFound = true;
            }
        }
        
        return $oddFound ? $length + 1 : $length;
    }
}

                                            
class Solution {
    func longestPalindrome(_ s: String) -> Int {
        var charCount = [Character: Int]()
        
        for char in s {
            charCount[char, default: 0] += 1
        }
        
        var length = 0
        var hasOdd = false
        
        for (_, count) in charCount {
            length += count / 2 * 2
            if count % 2 == 1 {
                hasOdd = true
            }
        }
        
        if hasOdd {
            length += 1
        }
        
        return length
    }
}

                                            
class Solution {
    fun longestPalindrome(s: String): Int {
        var count = 0
        val charCount = mutableMapOf<Char, Int>()

        for (char in s) {
            charCount[char] = charCount.getOrDefault(char, 0) + 1
        }

        var hasOdd = false
        for ((_, value) in charCount) {
            count += value
            if (value % 2 != 0) {
                count--
                hasOdd = true
            }
        }

        return if (hasOdd) count + 1 else count
    }
}

                                            
class Solution {
  int longestPalindrome(String s) {
    Map<String, int> charCount = {};
    
    for (int i = 0; i < s.length; i++) {
      String char = s[i];
      if (charCount.containsKey(char)) {
        charCount[char] = charCount[char]! + 1;
      } else {
        charCount[char] = 1;
      }
    }
    
    int palindromeLength = 0;
    bool hasOddCount = false;
    
    charCount.forEach((key, value) {
      palindromeLength += value ~/ 2 * 2;
      if (value % 2 == 1) {
        hasOddCount = true;
      }
    });
    
    if (hasOddCount) {
      palindromeLength++;
    }
    
    return palindromeLength;
  }
}

                                            
func longestPalindrome(s string) int {
    charCount := make(map[rune]int)
    for _, char := range s {
        charCount[char]++
    }
    
    palindromeLength := 0
    hasOdd := false
    
    for _, count := range charCount {
        palindromeLength += count
        if count%2 == 1 {
            palindromeLength--
            hasOdd = true
        }
    }
    
    if hasOdd {
        palindromeLength++
    }
    
    return palindromeLength
}

                                            
# @param {String} s
# @return {Integer}
def longest_palindrome(s)
    count = s.chars.tally
    palindrome_length = 0
    odd_count = false
    
    count.each do |_, c|
        if c % 2 == 0
            palindrome_length += c
        else
            palindrome_length += c - 1
            odd_count = true
        end
    end
    
    palindrome_length += 1 if odd_count
    
    return palindrome_length
end

                                            
object Solution {
    def longestPalindrome(s: String): Int = {
        val charCount = s.groupBy(identity).view.mapValues(_.size)
        var longestLen = 0
        var hasOdd = false
        for ((_, count) <- charCount) {
            longestLen += count / 2 * 2
            if (count % 2 == 1) hasOdd = true
        }
        if (hasOdd) longestLen + 1 else longestLen
    }
}

                                            
impl Solution {
    pub fn longest_palindrome(s: String) -> i32 {
        use std::collections::HashMap;

        let mut freq_map = HashMap::new();
        let mut odd_count = 0;

        for c in s.chars() {
            *freq_map.entry(c).or_insert(0) += 1;
        }

        for (_, freq) in freq_map {
            if freq % 2 == 1 {
                odd_count += 1;
            }
        }

        if odd_count > 0 {
            return s.len() as i32 - odd_count + 1;
        } else {
            return s.len() as i32;
        }
    }
}

                                            
defmodule Solution do
  @spec longest_palindrome(s :: String.t) :: integer
  def longest_palindrome(s) do
    freq_map = s
      |> String.graphemes()
      |> Enum.frequencies()
    
    total_length = freq_map
      |> Enum.reduce(0, fn {_, count}, acc -> 
        acc + div(count, 2) * 2
      end)
    
    if total_length < String.length(s) do
      total_length + 1
    else
      total_length
    end
  end
end

To solve this coding challenge, we need to understand how to construct the longest palindrome from a given string while respecting certain constraints. Here's a detailed explanation and the pseudocode.

Explanation

A palindrome is a string that reads the same forward and backwards. For example, "racecar" is a palindrome. To build the longest palindrome using characters from the given string

s

, the characters must mirror around a central point. This central point can optionally have one character if the length of the palindrome is odd.

Detailed Steps to Formulate the Solution

Counting Characters :

We first need to count the frequency of each character in the string

s

. A dictionary can be used for this purpose, where the keys are the characters and the values are the counts.

Even and Odd Counts :

Characters with even counts can all be used in the palindrome since they can be symmetrically placed around the center.
For characters with odd counts, all but one of the characters can be paired symmetrically. The leftover single character from one of the odd counts (if any) can be placed at the center of the palindrome.

Constructing the Palindrome Length :

Add up the counts of all characters that have even counts.
For characters with odd counts, add the highest even number they can contribute (i.e., count - 1).
If any character had an odd count, add 1 to the overall length to account for the potential single character at the center.

Constraints and Edge Cases:

If the string length is between 1 and 2000, our solution needs to efficiently handle this range.
Only consider lowercase and uppercase English letters.
Handle edge cases like strings with all characters being the same or only one character.

Pseudocode:

Below is the pseudocode breakdown with comments included for clarity:

                                            
# Function to find the length of the longest palindrome that can be built
function longestPalindrome(s):
# Dictionary to count the occurrence of each character
character_counts = {}

# Initialize variables to store the length of the palindrome and to check if an odd count is found
palindrome_length = 0
odd_count_found = False

# Iterate over each character in the string to count their occurrences
for character in s:
if character in character_counts:
# Increment the count for existing character
character_counts[character] += 1
else:
# Initialize count for new character
character_counts[character] = 1

# Iterate over the counted character frequencies
for count in character_counts.values():
if count % 2 == 0:
# If the count is even, add it directly to the palindrome length
palindrome_length += count
else:
# If the count is odd, add its largest even part to the length and set odd_count_found to True
palindrome_length += count - 1
odd_count_found = True

# If there was at least one odd count, add one to the palindrome length to place one odd character in the center
if odd_count_found:
return palindrome_length + 1
else:
# If no odd count was found, return the computed length
return palindrome_length

Step-by-Step Explanation in Pseudocode

Initialize Data Structures :

Start by creating a dictionary to store character counts. Initialize variables for the computed palindrome length and a flag to detect odd counts.

Count Characters :

Loop through each character in the input string, updating the dictionary with their counts. This ensures all character frequencies are recorded accurately.

Compute Palindrome Length :

Loop through the dictionary values (counts of each character). For each count:

If it’s even, add the whole count to
palindrome_length

.
If it’s odd, add the largest even part of the count (i.e., count - 1) to
palindrome_length

and mark that an odd count was found.

Finalize Length Calculation :

After processing all characters:

If any odd count was found, increment the palindrome length by 1 to place the central character.
Return the final computed length.

By following these steps, we ensure that the longest possible palindrome is constructed from the given string.