Algorithm
Problem Name: 409. Longest Palindrome
Given a string s which consists of lowercase or uppercase letters, return 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 that can be built is "a", whose length is 1.
Constraints:
1 <= s.length <= 2000sconsists of lowercase and/or uppercase English letters only.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int longestPalindrome(char* s) {
int n[52] = { 0 };
int i, k, odd;
while (*s) {
if (*s >= 'a') i = *s - 'a';
else i = *s - 'A' + 26;
n[i] ++;
s ++;
}
k = 0;
odd = 0;
for (i = 0; i < 52; i ++) {
odd |= n[i] % 2;
k += n[i] - (n[i] % 2); // can use part of them!!!
}
return k + odd;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int longestPalindrome(string s) {
int odd = 0;
unordered_map < char, int>m;
for(auto c: s) odd += m[c]++ % 2 ? -1 : 1;
return min(s.size(), s.size() - odd + 1);
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int longestPalindrome(String s) {
Map map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
int totalLength = 0;
boolean oddTaken = false;
for (Character key : map.keySet()) {
totalLength += (map.get(key) / 2) * 2;
if (!oddTaken && map.get(key) % 2 != 0) {
totalLength++;
oddTaken = !oddTaken;
}
}
return totalLength;
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const longestPalindrome = function (s) {
const set = new Set()
let counter = 0
for (let i = 0; i < s.length; i++) {
const currentChar = s[i]
if (set.has(currentChar)) {
counter++
set.delete(currentChar)
} else {
set.add(currentChar)
}
}
counter *= 2
if (set.size > 0) counter++
return counter
}
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: int
"""
from collections import Counter
out=even=sum(v for k,v in Counter(s).items() if v%2==0)
odd_big=[v for k,v in Counter(s).items() if v%2!=0 and v>1]
odd_small=[v for k,v in Counter(s).items() if v==1]
if len(odd_big)==1: out+=odd_big[0]
else:
out+=sum(odd_big)-len(odd_big)+1
if len(odd_small)==0 and len(odd_big)==0: out-=1
return out
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0409_LongestPalindrome
{
public int LongestPalindrome(string s)
{
var counts = new Dictionary < int, int>();
foreach (var ch in s)
{
if (!counts.ContainsKey(ch))
counts[ch] = 1;
else
counts[ch]++;
}
var result = 0;
var odd = 0;
foreach (var ch in counts.Keys)
{
odd |= counts[ch] & 1;
result += counts[ch] / 2;
}
return result * 2 + odd;
}
}
}
Input
Output