Java solution using boolean array to count pairs and non-paired char in one for-loop


  • 0

    The idea is clear that each pair of char can be used to form the longest palindrome.
    If there is any char is not paired, this char can be used as the center of the palindrome.

    public class Solution {
        public int longestPalindrome(String s) {
            if (s==null || s.length() ==0 ) return 0;
            boolean[] odds = new boolean[256];
            int max=0;
            int odds_count=0;
            for (char c : s.toCharArray()) { 
                if( odds[c] ) {
                    max+=2;
                    odds_count--;
                }
                else odds_count++;
                odds[c] = ! odds[c];
            }
            return odds_count > 0 ? max+1: max;
        }
    }
    

Log in to reply
 

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