C++ Solution


  • 0

    First count the occurrence of each character, then we go through the count, if a count is even we just add it to the result, else we store it into a vector, and keep track of the max odd count we've seen so far. Then we iterate through the vector of odd numbers, and add each count minus one to the result, since we want the result to be a palindrome as long as possible. Finally add the max odd count to the result.
    Any optimization is welcome.

        int longestPalindrome(string s) {
            unordered_map<char, int> m;
            for (char c: s)
                m[c]++;
            int res = 0, maxOdd = 0, seenMax = 0;    
            vector<int> odds;
            for (auto it=m.begin();it!=m.end();++it){
                if ((it->second)%2==0)
                    res += it->second;
                else {
                    maxOdd = max(maxOdd, it->second);
                    odds.push_back(it->second);
                }
            }
            for (int n : odds){
                if (n!=maxOdd || seenMax)
                    res += (n-1);
                else if (n==maxOdd && !seenMax)
                    seenMax = 1;
            }
            return res + maxOdd;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.