Easy to understand accepted solution with explanation


  • 8
    I

    First, characters are counted. Even occurring characters (v[i]%2 == 0) can always be used to build a palindrome. For every odd occurring character (v[i]%2 == 1), v[i]-1 characters can be used. Res is incremented if there is at least one character with odd occurrence number.

        int longestPalindrome(string s) {
            vector<int> v(256,0);
            for(int i = 0; i < s.size(); ++i)
               ++v[s[i]];
            int res = 0;
            bool odd = false;
            for(int i = 0; i < 256; ++i)
               if(v[i]%2 == 0)
                   res += v[i];
                else
                {
                   res += v[i] - 1;
                   odd = true;
                }
            if(odd)
              ++res;
            return res;
        }
    

  • 1
    A

    Thanks for your solution!
    It's easy to understand, but I have one question: why use v(256,0) instead of v(26,0)?


  • 0
    I

    Thanks for your question. Because, per problem statement, the string is case sensitive "Given a string which consists of lowercase or uppercase letters.."


  • 0
    A

    @i9r0k Thanks for your explanation! That's really helpful...
    But I have a follow-up question though (please bear with me): why choose the exact number of 256 instead of 52? (26 lower case and 26 upper case)


  • 0
    P

    @aw2013 Because in the v[s[i]], it contains not the char letter, it contains the Ascii number of 'ABCD....', such that just 52 sized vector is not enough, the lower case of 'a' begins with Ascii number 97. (I think 128 is enough)


Log in to reply
 

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