409. Longest Palindrome
1. Description
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.
2. Example
Example 1:
Input: s = “abccccdd”
Output: 7
Explanation:
One longest palindrome that can be built is “dccaccd”, whose length is 7.
Example 2:
Input: s = “a”
Output: 1
Example 3:
Input: s = “bb”
Output: 2
3. Constraints
- 1 <= s.length <= 2000
- s consits of lower-case and/or upper-case English letters only.
4. Solutions
My Accepted Solution
n = i_str.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution
{
public:
// int longestPalindrome(string s)
int longestPalindrome(string &i_str)
{
vector<int> letterTimes(256); // char set
for(int i = 0; i < i_str.size(); i++)
letterTimes[i_str[i]]++;
// even number char could construct a palindrome
int result = 0;
for(int i = 0; i < letterTimes.size(); i++)
{
if(letterTimes[i] & 1)
result += letterTimes[i] - 1;
else
result += letterTimes[i];
}
// we could add another char at the middle of the palindrome, but we shuold check whether we have enough chars
// since all chars may have even numbers
return min(result + 1, (int)i_str.size());
}
};