Java Solution and Explanation on Why it is the way it is


  • 0
    R

    Before I get down to the explanation, let me give the code first

    public int longestPalindrome(String s) {
            
            if(s == null || s.isEmpty()){
                return 0;
            }
            
            int[] count = new int['z'-'A'+1];
            
            for(int i=0;i < s.length();i++){
                char c = s.charAt(i);
                ++count[c-'A'];
            }
            
            int odd = 0;
            for(char c = 'A' ; c <= 'z';c++){
                if( (count[c-'A'] & 1) != 0){
                    ++odd;
                }
            }
            
            return s.length()-odd + (odd > 0 ? 1: 0);   
        }
    
    

    Now let me explain the solution and also why it works.

    A palindrome can have odd or even number of characters.

    a. When the length of palindrome is even, all the characters must have appeared even number of times.
    b. When the length of palindrome is odd, all characters must have appeared even number of times, but one character would have appeared odd number of times.

    So, first we calculate the count of characters that have appeared odd number of times. now we can still use these characters in the palindrome, but we cannot use all instances. We can only use even number of occurrences of it.

    ex: if 'a' appears 3 times, we can still use 'a' to form a palindrome by taking 2 of them.

    So we subtract the count of characters that are occurring odd number of times.

    Once that is calculated, we can still use one of the characters odd number of times, we add one to the length of the longest palindrome if the number of characters which have appeared odd number times is more than zero.

    Lets take an example:

    Given String is "aaab".

    When we calculate the count, we get

    a = 3
    b = 1

    so we have two characters which appear odd number of times. so 4 - 2 = 2.

    But note that the longest palindrome that can be formed is of length 3.

    meaning, we can use one character which has appeared odd number of times as part of the palindrome.

    Hence we add one to the length.


  • 0
    D

    @RepentThySins

    • Given "abba", the longest palindrome substring is 4, itself;
    • Given "abab", the longest palindrome substring is 3, aba, bab

    But your algorithm would return 4 for both cases. Because you do not consider the order of the sequence.

    Or I misunderstand you?


Log in to reply
 

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