LongestPalindrome [source code]

public class LongestPalindrome {
    public int longestPalindrome(String s) {
        if (s.length() <= 1) return s.length();
        char[] letters = s.toCharArray();
        int[] counts = new int[52];
        for (int c : letters) {
            if (c <= 'Z') counts[c - 'A']++;
            else counts[c - 'a' + 26]++;
        }
        int res = 0;
        boolean hasOdd = false;
        for (int i : counts) {
            if (i % 2 == 0) res += i;
            else {
                hasOdd = true;
                res += i - 1;
            }
        }
        return hasOdd ? res + 1 : res;
    }

    public static void main(String[] args) {
        LongestPalindrome tester = new LongestPalindrome();
        String input1 = "civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth";
        String input2 = "abccccdd";
        String input3 = "bb";
        assert tester.longestPalindrome(input1) == 983;
        assert tester.longestPalindrome(input2) == 7;
        assert tester.longestPalindrome(input3) == 2;
        System.out.println(tester.longestPalindrome(input2));
    }
}

看起来不算难的一个题目, 结果做起来也是费了不少功夫.
这个题目的难点在于需要判断的地方有很多, 比如光是最后是否需要加这个1都要单独进行判断;

最后的速度是9ms, 94%, 还算可以接受;
看了一下, submission 最优解的代码跟我的几乎是一样的;

2018-04-22 16:32:33 回头看看这题其实还挺有意思的; 可能是我思维定式了, 现在一看到说是palindrome立刻就想到中心发散. 这题根本不需要这样; 这题因为其实没有规定任何的顺序; 所以最后靠的数学分析就行了;

数学上的逻辑还是很简单的, 主要还是怕踩想的太复杂了这个坑;

注意一个常识性的问题, 以前一直以为'A' 比'a' 大, 做这个问题的时候才发现一直以来的这个印象都是错的;

java> (int) 'a'  
java.lang.Integer res2 = 97  
java> (int) 'A'  
java.lang.Integer res3 = 65

另外新提一个概念: Verbal Logic: 尤其是像这种逻辑比较复杂的题目, 光是盯着代码, 写一行想一行的做法可能就效果比较低, 比较好的做法是, 要先从高层面上, 自己verbally 总结出来你想要表达的逻辑: 一般用这种形式: 如果...那么我就应该..., 或者用automaton 的概念来理解, 如果我是这个 state, 我应该进行什么操作, transmit 到什么 state 去;

这题的一个核心其实就是count pair, 在 discussion 上面有这么一个用 set 做得答案:

public int longestPalindrome(String s) {  
        if(s==null || s.length()==0) return 0;  
        HashSet<Character> hs = new HashSet<Character>();  
        int count = 0;  
        for(int i=0; i<s.length(); i++){  
            if(hs.contains(s.charAt(i))){  
                hs.remove(s.charAt(i));  
                count++;  
            }else{  
                hs.add(s.charAt(i));  
            }  
        }  
        if(!hs.isEmpty()) return count*2+1;  
        return count*2;  
}

总体来说意思其实差不多, 不过这个counter vote的思路有一个好处就是不用单独做一个 flag 来确定最后需不需要+1;

discussion 上面, 对于我这个算法最后的1pass 给出了不同的做法:

for (int i = 0; i < 26; i++){  
    res+=(lowercase[i]/2)*2;  
    res+=(uppercase[i]/2)*2;  
}  
return res == s.length() ? res : res+1;

这个做法有两大优势:

1. 每一个 iteratoin 不用对 count 的值判断奇偶性, 直接利用整除再*2来统一处理;
2. 不用保留hasOdd flag, 只要最后所有的 pair 数量没有达到 s 的长度, 那么肯定就有因为 odd number of occurrence而被遗漏的 element, 所以直接就可以+1;

discussion其他的答案基本都大同小异了;

Problem Description

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:

• Assume the length of given string will not exceed 1,010.

Example:

Input:  
"abccccdd"  

Output:  
7  

Explanation:  
One longest palindrome that can be built is "dccaccd", whose length is 7.

Difficulty:Easy
Category:Algorithms
Acceptance:45.27%
Contributor: LeetCode
Companies
google
Related Topics
hash table
Similar Questions
Palindrome Permutation