in c++ 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. The letters are case sensitive ie. a != A Your solution should be O(n)!

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

Explanation: The longest palindrome that can be built is "a", whose length is 1.

Constraints

<= s.length <= 2000

s consists of lowercase and/or uppercase English letters only.

Discussion:

Your first instinct might be to find all of the permutations of the characters starting a length 1 and then figure out which are palindromes. If you do that you you are into factoral space! So obviously that is a no go.

What to do?

Without giving the problem away, you need to think about the characteristics of a palindrome. Start with "aa". What is special about this versus "ab" and "aabbaa" versus "aabba".

Second, you will need to use an STL unordered map.

#include #include #include #include #include

template // most generic way to set up a print function // can then be used with every map. save it for later!!!! void print_map(std::unordered_map const &m) { for (auto const &pair: m) { std::cout << "{" << pair.first << ": " << pair.second << "} "; } }

int longestPal(std::string inString){ //// your code here ???? return maxLength; }

int main() { // read in the string of characters std::string inString = ""; //freopen("data.txt","r",stdin); std::cin >> inString;

// call longestPal auto maxLength = longestPal(inString); // output std::cout << maxLength << std::endl; return 0; }