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

• 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);
}

• 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);
}

• 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.

Correct me if I am wrong!

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

• @StefanPochmann Oh found that! good night!

• 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);
}

• 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?

• it can't be added with int?

It can.

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.

• 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?

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

I don't know you can do return odds + bool(odds), which returns an int.

• @lee215 Nice job

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