Algorithm to Compute the Length of the Longest Palindrome String

  • 时间:2020-10-12 15:39:01
  • 分类:网络文摘
  • 阅读:90 次

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;
    }
}

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
班里的新鲜事作文400字  写人作文顽童校长作文800字  诚信做人作文550字  秋天的礼物作文500字  贤妻良母发表日志:秋雨秋思何茫茫  关于元宵节的作文300字  写人作文“无赖”潘胜豪作文400字  我的读书生活700字  第一次洗红领巾作文100字  咀嚼人生作文1000字 
评论列表
添加评论