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:
7Explanation:
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) —
推荐阅读:后廿九日复上宰相书原文及翻译 争臣论原文及翻译 进学解原文及翻译 与韩荆州书原文及翻译 为徐敬业讨武曌檄原文及翻译 滕王阁序原文及翻译 谏太宗十思疏原文及翻译 红梅本来有几粒糖 摸黄球白球可能性的问题 如果要准时到达需要多少小时
- 评论列表
-
- 添加评论