Java with explanation


  • 0
    J

    So after thinking about this for like 10 minutes, I realized that you can always use letters that occur an even number of times. For letters that occur an odd numbers of times, assume that we use the largest odd occurence (since we can put that in the middle of the palindrome). Then for the rest of the odd occurences, we can subtract 1 so that it's even and can be used for the palindrome. Here's my Java code:

    public class Solution {
        public int longestPalindrome(String s) {
            // letters that occur even number of times can always be used to build a palindrome
            // letters that occur odd numbers of times, pick the largest odd occurence 
            // (since it can go in the middle of the palindrome)
            
            int[] occurence = new int[256];
            
            for(char c : s.toCharArray()){
                occurence[c]++;
            }
            
            // keeps track of length
            int sum = 0;
            
            // add largest odd occurence to the length
            int maxOdd = 0;
            int maxIndex = 0;
            for(int i = 0; i < 256; i++){
                if(occurence[i] % 2 == 1 && occurence[i] > maxOdd){
                    maxOdd = occurence[i];
                    maxIndex = i;
                }
            }
            occurence[maxIndex] = 0;
            sum += maxOdd;
            
            // sum all the even occurences
            for(int i = 0; i <256; i++){
                int val = occurence[i] % 2 == 0 ? occurence[i] : occurence[i] - 1;
                sum += val;
            }
            
            return sum;
        }
    }
    
    

Log in to reply
 

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