Solution 1 - Greedy Counting

Use as many character pairs as possible; if any odd remains, place one in the center.

TimeComplexity: O(n)

SpaceComplexity: O(k)

""" 0409.1 - Longest Palindrome - Solution 1 - Greedy Counting """

from collections import Counter

class Solution:
    def longestPalindrome(self, s: str) -> int:
        c = Counter(s)
        res = 0
        odd = False
        for v in c.values():
            res += v // 2 * 2
            if v % 2 == 1:
                odd = True
        return res + (1 if odd else 0)

function longestPalindrome(s){
 const m=new Map();
 for(const ch of s) m.set(ch,(m.get(ch)||0)+1);
 let res=0, odd=false;
 for(const v of m.values()){ res += v - (v%2); if(v%2) odd=true; }
 return res + (odd?1:0);
}

function longestPalindrome(s:string):number{
 const m:Map<string,number>=new Map();
 for(const ch of s) m.set(ch,(m.get(ch)??0)+1);
 let res=0, odd=false;
 for(const v of m.values()){ res += v - (v%2); if(v%2) odd=true; }
 return res + (odd?1:0);
}

package main

func longestPalindrome(s string) int {
	cnt := map[rune]int{}
	for _, ch := range s {
		cnt[ch]++
	}
	res := 0
	odd := false
	for _, v := range cnt {
		res += v / 2 * 2
		if v%2 == 1 {
			odd = true
		}
	}
	if odd {
		res++
	}
	return res
}

func main() {}

use std::collections::HashMap;

fn longest_palindrome(s: &str) -> i32 {
	let mut cnt: HashMap<char, i32> = HashMap::new();
	for ch in s.chars() { *cnt.entry(ch).or_insert(0) += 1; }
	let mut res: i32 = 0;
	let mut odd = false;
	for v in cnt.values() {
		res += (v / 2) * 2;
		if v % 2 == 1 { odd = true; }
	}
	res + if odd { 1 } else { 0 }
}

fn main() {}

Solution 2 - Running Pair Count

Whenever a char’s count becomes even, add 2 to the answer; at end add 1 if any leftover.

TimeComplexity: O(n)

SpaceComplexity: O(k)

from collections import defaultdict

class Solution:
    def longestPalindrome(self, s: str) -> int:
        cnt = defaultdict(int)
        res = 0
        for ch in s:
            cnt[ch] += 1
            if cnt[ch] % 2 == 0:
                res += 2
        return res + (1 if res < len(s) else 0)

function longestPalindrome2(s:string):number{
 const cnt:Map<string,number>=new Map();
 let res=0;
 for(const ch of s){
  cnt.set(ch,(cnt.get(ch)??0)+1);
  if((cnt.get(ch) as number)%2===0) res+=2;
 }
 return res + (res<s.length?1:0);
}

package main

func longestPalindrome2(s string) int {
	cnt := map[rune]int{}
	res := 0
	for _, ch := range s {
		cnt[ch]++
		if cnt[ch]%2 == 0 {
			res += 2
		}
	}
	if res < len(s) {
		res++
	}
	return res
}

func main() {}

use std::collections::HashMap;

fn longest_palindrome2(s: &str) -> i32 {
	let mut cnt: HashMap<char, i32> = HashMap::new();
	let mut res: i32 = 0;
	for ch in s.chars() {
		let e = cnt.entry(ch).or_insert(0);
		*e += 1;
		if *e % 2 == 0 { res += 2; }
	}
	if res < s.len() as i32 { res + 1 } else { res }
}

fn main() {}

0409 - Longest Palindrome

Solution 1 - Greedy Counting

Solution 2 - Running Pair Count