Simple Java Solution in One Pass


  • 10
    N

    Count duplicates in the pass, then check if we have an extra character to fix in the middle.

    public int longestPalindrome(String s) {
            boolean[] map = new boolean[128];
            int len = 0;
            for (char c : s.toCharArray()) {
                map[c] = !map[c];         // flip on each occurrence, false when seen n*2 times
                if (!map[c]) len+=2;
            }
            if (len < s.length()) len++; // if more than len, atleast one single is present
            return len;
        }
    

  • 0
    F

    Great, I was doing basically the same but with a 59 len array.

    used a bitmask to convert the chars since they appeared to be all alphabet chars:

    public class Solution {
        public int longestPalindrome(String s) {
            boolean chars[] = new boolean[59];
            int pairs = 0;
            for(char c : s.toCharArray()){
                c &= 0x3F;
                if(chars[c]) pairs++;
                chars[c] = !chars[c];
            }
            pairs *= 2;
            if(pairs < s.length())pairs++;
            return pairs;
        }
    }
    

  • 0
    L

    I got similar solution with using int array instead of boolean. I think using a boolean array is brilliant, however it seems to be running slower than using int - int took 9ms whereas boolean took 11ms. Does flipping a boolean slower than integer increment?

    public class Solution {
        public int longestPalindrome(String s) {
            int[] count = new int[128];
            int len = 0;
            for (char c : s.toCharArray()) {
                if ((++count[c] & 1) == 0) len += 2;
            }
            return len < s.length() ? len + 1 : len;
        }
    }
    

  • 0
    W

    good solution


Log in to reply
 

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