Following @StefanPochmann's solution, the following Java code runs in O(n).

- odd: number of characters which appears odd number of times
- Use s.toCharArray() for fastest string walking (assuming that the string is long enough)
- Attention: odd can be zero. In this case, we should return s.length(), and this explains the last line.

```
public int longestPalindrome(String s) {
int[] count = new int['z' - 'A' + 1];
for (char c : s.toCharArray()) count[c - 'A']++;
int odd = 0;
for (char c = 'A'; c <= 'z'; c++) odd += (count[c - 'A'] & 1);
return s.length() - odd + (odd > 0 ? 1 : 0);
}
```