Longest Palindrome

Problem Statement

LeetCode-409: Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, “Aa” is not considered a palindrome here.

Approach

The idea is to count the frequency of each character in the string. A few observations can be made to solve this problem:

1. A palindrome can have at most one character with an odd frequency.
2. All the other characters in the palindrome should have an even frequency.
3. If a character has an odd frequency, we can include all the characters except one in the palindrome.
4. If a character has an even frequency, we can include all the characters in the palindrome.

To implement the above approach, we can use a Map or array to store the frequency of characters. However, we don’t really have to retain the individual frequencies. Instead, we can use a Set to store only the characters themselves with odd frequency.

Here is how the approach works:

1. Iterate through the characters of the string.
2. If the character is already present in the set, remove it from the set and increment the result by 2 as now we know the current character is present at-least twice.
3. Otherwise, add it to the set.
4. Finally, if the set is not empty, increment the result by 1 - based on the fact that a palindrome can have at most one character with an odd frequency.

Implementation

Based on the approach mentioned above, following is a java implementation:

public int longestPalindrome(String s) {
    Set<Character> freq = new HashSet<>();
    int result = 0;

    for(char ch : s.toCharArray()){
        // If the character is already present in the set, 
        // remove it from the set and increment the result by 2
        // contributing to 1 pair of even frequency characters.
        if(freq.contains(ch)){
            freq.remove(ch);
            result+=2;
        }else{
            freq.add(ch);
        }
    }       
    if(!freq.isEmpty()){
        result++;
    }
    return result;
}

Complexity Analysis

The overall time complexity for this approach is \(O(n)\) where \(n\) is the length of the input string. The space complexity is constant i.e. \(O(1)\) as at max 52 characters (lowercase + uppercase) can be present in the set.