LC409. Longest Palindrome

Approach 1: Counter

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

Complexity

Time: $O(n)$
Space: $O(n)$

Approach 1: Set

class Solution:
    def longestPalindrome(self, s: str) -> int:
        solo_chars = set()
        res = 0
 
        for c in s:
            if c in solo_chars:
                solo_chars.remove(c)
                res += 2
            else:
                solo_chars.add(c)
        
        if solo_chars:
            res += 1
        
        return res

Complexity

Time: $O(n)$
Space: $O(n)$

Other Languages

Swift

class Solution {
    func longestPalindrome(_ s: String) -> Int {
        var soloChars: Set<Character> = []
        var res = 0
 
        for c in s {
            if soloChars.contains(c) {
                soloChars.remove(c)
                res += 2
            } else {
                soloChars.insert(c)
            }
        }
 
        if !soloChars.isEmpty {
            res += 1
        }
 
        return res
    }
}