Algorithm to Compute the Length of the Longest Palindrome String

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters. This is case sensitive, for example “Aa” is not considered a palindrome here. Assume the length of given string will not exceed 1,010.

Example: Input: “abccccdd”

Output:
7

Explanation:
One longest palindrome that can be built is “dccaccd”, whose length is 7.

A palindrome is a string that its reverse is the same string.

Greedy Algorithm to Compute Longest Palindrome

The first run is to count the occurences of each character and store the frequencies in a hash map e.g. unordered_map in C++. Then, when a character appears even number of times, we know we can use this letter to extend the candidate string into a palindrome by both sides of the strings – we update the length by the number of the characters. If, however, a character appears odd number of times e.g. t times, we still can increase the length by (t-1). However, at the end, the length need to add one because the middle of the palindrome can be a single character.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> count;
        for (const auto &ch: s) {
            if (count.find(ch) == count.end()) {
                count[ch] = 1;
            } else {
                count[ch] ++;
            }
        }
        int odd = 0, sum = 0;
        for (auto it = count.begin(); it != count.end(); it ++) {
            if (it->second % 2 == 0) {
                sum += it->second;
            } else {
                odd = 1;
                sum += it->second - 1;
            }
        }
        return sum + odd;
    }
};

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> count;
        for (const auto &ch: s) {
            if (count.find(ch) == count.end()) {
                count[ch] = 1;
            } else {
                count[ch] ++;
            }
        }
        int odd = 0, sum = 0;
        for (auto it = count.begin(); it != count.end(); it ++) {
            if (it->second % 2 == 0) {
                sum += it->second;
            } else {
                odd = 1;
                sum += it->second - 1;
            }
        }
        return sum + odd;
    }
};

The time complexity is O(N) and the space complexity is also O(1) where N is the length of the input string. It is O(1) space because the string contains only uppercase and lowercase characters i.e. we can use a int[128] to store the frequencies instead – which obviously gives O(1) space complexity.

The Same Algorithm can be implemented in the following Java Program where to iterate over a Java Map (e.g. hashmap) can be done via Map.Entry and entrySet:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> data = new HashMap<>();
        for (char n: s.toCharArray()) {
            data.put(n, data.getOrDefault(n, 0) + 1);
        }
        int odd = 0, ans = 0;
        for (Map.Entry<Character, Integer> entry: data.entrySet()) {
            int cnt = entry.getValue();
            if (cnt % 2 == 0) {
                ans += cnt;
            } else {
                ans += cnt - 1;
                odd = 1;
            }
        }
        return ans + odd;
    }
}

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> data = new HashMap<>();
        for (char n: s.toCharArray()) {
            data.put(n, data.getOrDefault(n, 0) + 1);
        }
        int odd = 0, ans = 0;
        for (Map.Entry<Character, Integer> entry: data.entrySet()) {
            int cnt = entry.getValue();
            if (cnt % 2 == 0) {
                ans += cnt;
            } else {
                ans += cnt - 1;
                odd = 1;
            }
        }
        return ans + odd;
    }
}

See also: Teaching Kids Programming – Longest Palindrome String From Set of Characters

–EOF (The Ultimate Computing & Technology Blog) —