[ Detail ] Beating 94.71% Solution with Bucket Time O(n), Space O(n)


  • 0

    As follows, using int[52] bucket to do the letter count, which significantly reduces the running time compared with HashMap implementation (which would be placed around bottom 10% among all accepted submissions). With the words count, the longest Palindrome come to odd_letter>0 ? 1+even_letter_count : even_letter_count.

    public int longestPalindrome(String s) {
        int[] l_en = new int[52];
        int one_odd_cnt = 0;
        int even_cnt = 0;
        
        for (char ch: s.toCharArray()){
            if(ch>=97){
                l_en[26 + ch -'a']++;
            }else{
                l_en[ch-'A']++;
            }
        }
        
        for (int cnt : l_en){
            if (cnt%2==0 && cnt!=0){
                even_cnt+=cnt;
            }else if(cnt>=1){
                if(cnt==1){
                    one_odd_cnt++;
                }else{
                    even_cnt+=cnt-1;
                    one_odd_cnt++;
                }
            }
        }
        
        return one_odd_cnt>0 ? 1+even_cnt : even_cnt;
    }

Log in to reply
 

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