Simple array based Java solution O(n)


  • 0
    J
    public class Solution {
        public int longestPalindrome(String s) {
            if(s.isEmpty()){return 0;}
    
            int ans = 0;
            boolean odd = false; 
            int[] letters = new int[52];
                   
            for(char c: s.toCharArray()){
                if(c >= 97){
                    letters[c-72]++; 
                }else{
                    letters[c-65]++;
                }        
            }
            
            for(int i = 0; i < letters.length;i++){
                if(letters[i] != 0){
                    if(letters[i] % 2 == 0){
                        ans += letters[i];
                    }else{
                        ans += letters[i] - 1;
                        odd = true;
                    } 
                }
            }
            
            ans += odd ? 1 : 0;
            return ans;
        }
    }
    

    The idea is to first count how many characters are in the string and store in a char array. Then pass over the new array and check if the value stored is even or odd. If the number is even, add it to the answer and if odd, subtract 1 and add to the answer. At the end check if at least one character had an odd count. If so add 1 more to the answer.

    It works because if there is an even count of the character, it is a palindrome. If it is odd, then taking out one character makes it a palindrome. With this approach, we ignore the combination of an odd length palindrome. This is compensated for at the end where we add 1 if there is at least an existence of an odd count character.

    There are probably ways to speed this up a bit more.


Log in to reply
 

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