Easy Java solution with explanation


  • 0
    L

    The idea is the following:

    1. If there are one or more characters that appear only once: use 1 for all of their occurences.
    2. If there are even number of characters, add them all
    3. If there are odd numbers of characters, then use the even part and use 1 for the remaining only if 0.) has not been considered already.

    let us take an example: Input:
    "abccccdd"

    Iterate over all unique characters:

    a) Initially, len=0
    a and b appear just once so we should do len=1 as either of them will keep the same length.

    b) c is 4 so add len +=4

    c) d is 2 so add len += 2

    Total is 7

    Another example : "addd"

    for a -> len =1
    for d -> len =2 ( because len of 1 has already been considered so no point of adding as any number that as a count of 1 should be treated equally)

    Here is the code:

    public int longestPalindrome(String s) {
            if(s==null) {
                return 0;
            }
            
            int[] arr = new int[58];//there are 6 extra characters in between A-Z and a-z.
            for(char c : s.toCharArray()) {
               arr[c-'A']++;
            }
    
            boolean one=false;
            int len = 0;
            for(int i=0;i<arr.length;i++) {
                int count = arr[i];
                if(count==0) {
                    continue;
                }
                if(count==1) {
                    one = true;
                }
                else if(count%2!=0) {
                    one = true;
                    len += (count-1); //get the even number.
                }
                else if(count%2==0) {
                    len += count;
                }
            }
            
            if(one) {
                len++;
            }
            
            return len;
            
        }
    

  • 0
    L

    I figured that I could make it more concise as it beat 90% of the Java submissions.

        public int longestPalindrome(String s) {
            if(s==null) {
                return 0;
            }
            
            int[] arr = new int[58];//there are 6 extra characters in between.
            for(char c : s.toCharArray()) {
               arr[c-'A']++;
            }
            int oddCount=0;
            for(int i=0;i<arr.length;i++) {
                if(arr[i]%2!=0) {
                    oddCount++;
                }
            }
            return Math.min(s.length(),s.length()-oddCount+1);
            
        }
    

Log in to reply
 

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