Longest Palindrome - Video Solutions

Problem Overview: Given a string of uppercase and lowercase letters, determine the length of the longest palindrome that can be built using those characters. Characters are case-sensitive, so 'A' and 'a' count as different letters. You can rearrange the characters in any order, but each character can only be used as many times as it appears.

Approach 1: Frequency Counting (O(n) time, O(k) space)

This approach uses a hash table to count how many times each character appears in the string. A palindrome works by pairing identical characters symmetrically around the center. For every character with frequency f, you can use f / 2 pairs, contributing 2 * (f / 2) characters to the palindrome length. If any character has an odd frequency, one leftover character can be placed in the center of the palindrome. Iterate through the frequency map, sum all even contributions, and add one extra character if any odd count exists. This approach is straightforward and works for any character set because the hash map dynamically tracks frequencies.

The key insight is that palindrome construction only cares about pairs of characters. Every pair contributes two characters to the final length. Odd counts are mostly usable except for one leftover character, and only one such leftover can occupy the center. The algorithm scans the string once to build the frequency map and once more to compute the length, giving O(n) time complexity with O(k) space where k is the number of unique characters.

Approach 2: Set Usage for Odd Counting (O(n) time, O(k) space)

This method tracks characters with odd occurrences using a set. Iterate through the string and toggle each character in the set: insert it if it's not present, remove it if it already exists. At the end of the scan, the set contains exactly the characters with odd frequencies. The longest palindrome uses all characters except the extra ones from odd counts. If the set size is odd, then odd - 1 of those characters must lose one occurrence to form pairs. The palindrome length becomes n - max(0, odd - 1).

This solution works because each toggle operation effectively pairs characters as they appear. Characters appearing an even number of times cancel out of the set. Only odd counts remain. The approach uses constant-time set operations and a single pass over the string, making it efficient for problems involving parity tracking. It also demonstrates a clean application of greedy reasoning with character pairing and leverages fast membership checks from a hash table based structure.

Recommended for interviews: The frequency counting approach is the most commonly expected solution. It clearly demonstrates understanding of palindrome structure and character pairing while keeping the logic easy to explain. The set-based approach is equally optimal and sometimes preferred for its elegance, but interviewers usually expect candidates to first reason about frequency counts in a string problem like this.