What are the odds? (Python & C++)


  • 42

    I count how many letters appear an odd number of times. Because we can use all letters, except for each odd-count letter we must leave one, except one of them we can use.

    Python:

    def longestPalindrome(self, s):
        odds = sum(v & 1 for v in collections.Counter(s).values())
        return len(s) - odds + bool(odds)
    

    C++:

    int longestPalindrome(string s) {
        int odds = 0;
        for (char c='A'; c<='z'; c++)
            odds += count(s.begin(), s.end(), c) & 1;
        return s.size() - odds + (odds > 0);
    }
    

    Similar solutions (I actually like the use solutions better than the above, but I'm just so fond of my topic title :-)

    def longestPalindrome(self, s):
        use = sum(v & ~1 for v in collections.Counter(s).values())
        return use + (use < len(s))
    
    def longestPalindrome(self, s):
        counts = collections.Counter(s).values()
        return sum(v & ~1 for v in counts) + any(v & 1 for v in counts)
    
    int longestPalindrome(string s) {
        int use = 0;
        for (char c='A'; c<='z'; c++)
            use += count(s.begin(), s.end(), c) & ~1;
        return use + (use < s.size());
    }
    
    int longestPalindrome(string s) {
        vector<int> count(256);
        for (char c : s)
            ++count[c];
        int odds = 0;
        for (int c : count)
            odds += c & 1;
        return s.size() - odds + (odds > 0);
    }
    
    int longestPalindrome(string s) {
        vector<int> count(256);
        int odds = 0;
        for (char c : s)
            odds += ++count[c] & 1 ? 1 : -1;
        return s.size() - odds + (odds > 0);
    }

  • 0
    W

    Since we know the string consists of lowercase or uppercase letters, count[0] can be used for counting odds.

    int longestPalindrome(const string &s) {
        int count[128]{};
        for (auto c : s) ++count[c];
        for (auto num : count) count[0] += num & 1;
        return s.size() - count[0] + (count[0] > 0);
    }
    

    Here is a shorter edition:

    int longestPalindrome(const string &s) {
        int count[128]{};
        for (auto c : s) count[0] += ++count[c] & 1 ? 1 : -1;
        return s.size() - count[0] + (count[0] > 0);
    }
    

  • 0

    Hi Stefan,

    Your solution seems to be O(('z' - 'A')n) and O(1).

    If you use an array with 'z' - 'A' size, the space is higher but the runtime is better when n is large.

    eg: if n is a million long, your algo. will run several million characters. At the same time, if there is a space, the runtime will be a million + the size of extra space.

    That's a tradeoff~

    Correct me if I am wrong!


  • 0

    @XiangyuLi926 In most of my solutions I'm already doing that.


  • 0

    @StefanPochmann Oh found that! good night!


  • 0
    R

    Java version of one of the 7th solution (only 5 lines and 13 ms!)

    public int longestPalindrome(String s) {
            int[] count = new int[256];
            int odds = 0;
            for (int v = 0; v < s.length(); v++)
                odds += (++count[s.charAt(v)] & 1) == 1 ? 1 : -1;
            return s.length() - odds + (odds > 0 ? 1 : 0);
        }
    

  • 0
    R

    hey I know

    return len(s)-odds+bool(odds)
    

    is a good idea.
    but bool(odds) returns True or False, it can't be added with int?


  • 1

    @rawmy12 said in What are the odds? (Python & C++):

    it can't be added with int?

    It can.


  • 1

    I made it 1-linear:
    Count odds:

        def longestPalindrome(self, s):
            return len(s) - max(sum(v & 1 for v in collections.Counter(s).values()) - 1, 0)
    

    Count evens:

        def longestPalindrome(self, s):
            return min(sum(v & ~1 for v in collections.Counter(s).values()) + 1, len(s))
    

    Edited after Stefan's suggestion below.


  • 0

    @lee215 said in What are the odds? (Python & C++):

    1-linear

    That always irritates me :-)
    (I only know it from algebra, e.g., "a multilinear map of k variables is called a k-linear map")

    Nice solutions... I especially like the second one (but I think ~1 would be a little clearer than -2).

    Why do you use list(s) instead of just s, though?


Log in to reply
 

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