Leetcode: 409. Longest Palindrome
- Primary idea: Count number of character with even and odd frequencies. Adjust the final result depending on if there is character with odd frequencies.
- Time Complexity: O(n)
- Space Complexity: O(n)
func longestPalindrome(_ s: String) -> Int {
// Dictionary storing occurence frequencies of characters in the the string
var frequencies = [Character: Int]()
// Calculate the occurence frequencies for all characters
for ch in s { frequencies[ch, default: 0] += 1 }
var result = 0
var hasOdd = false
// Count characters with even and odd frequencies
// adjust hasOdd flag if there is character with odd frequencies
for (_, el) in frequencies.enumerated() {
if el.value % 2 == 0 {
result += el.value
} else {
hasOdd = true
result += el.value - 1
}
}
return result + (hasOdd ? 1 : 0)
}