LeetCode Entry

409. Longest Palindrome

04.06.2024 easy 2024 kotlin rust

Max palindrome length from chars

409. Longest Palindrome easy blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/628

Problem TLDR

Max palindrome length from chars #easy

Intuition

Don’t mistaken this problem with find the longest palindrome, because this time we need to build one. (I have spent 5 minutes solving the wrong problem)

To build a palindrome, we need even counts of chars and at most one odd.

Approach

• we can use groupBy, sumBy and any
• f & 1 operation will convert any odd number into 1

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\), but O(n) for the groupBy solution, which can be optimized

Code

    fun longestPalindrome(s: String): Int =
        s.groupBy { it }.values.run {
            2 * sumBy { it.size / 2 } +
            if (any { it.size % 2 > 0 }) 1 else 0
        }

    pub fn longest_palindrome(s: String) -> i32 {
        let (mut freq, mut res, mut o) = (vec![0;128], 0, 0);
        for b in s.bytes() { freq[b as usize] += 1 }
        for f in freq { o |= f & 1; res += f / 2 }
        2 * res + o
    }