Title: Longest PalindromeSource: leetcode.com
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 1:
Input:
“abccccdd”
Output:
7
Explanation:
One longest palindrome that can be built is “dccaccd”, whose length is 7.
Example 2:
Input: “cccddd”
Output: 5
Python solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: int """ d = {} # create a dictionary for each letter and its occurrence for c in s: if c in d: d[c] += 1 else: d[c] = 1 keyset = d.keys() ans = 0 flag = False #print mx for key in keyset: #print key, d[key] if (d[key] & 1) == 0: # the count for current key is even. add it to length ans += d[key] del d[key] #print "if" else: # count of current char is odd, add a 1 less of its occurrence ans += (d[key] - 1) flag = True #print "else" if flag: # +1 for one of the odd occurrence character(s) ans += 1 return ans |
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
/* https://leetcode.com/problems/longest-palindrome/ */ import java.util.Map; import java.util.HashMap; import java.util.Collections; import java.util.List; import java.util.ArrayList; import java.util.Comparator; public class LongestPalindrome { public static void main(String args[]) { //String s = "abccccdd"; String s = "civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"; LongestPalindrome l = new LongestPalindrome(); System.out.println(l.longestPalindrome(s)); } public int longestPalindrome(String s) { Map<Character, Integer> map = new HashMap<>(); for(int i=0;i<s.length();++i) { char a = s.charAt(i); if(!map.containsKey(a)) { map.put(a, 1); } else { map.put(a, map.get(a)+1); } } List<Integer> list = new ArrayList<>(); for(Map.Entry<Character, Integer> entry : map.entrySet()) { list.add(entry.getValue()); } Comparator<Integer> comparator = Collections.reverseOrder(); Collections.sort(list, comparator); System.out.println(list); boolean odd = false; int count = 0; for(int i=0;i<list.size();++i) { if(list.get(i)%2==0) { count+=list.get(i); } else if(!odd) { count+=list.get(i); odd = true; } else { count+= list.get(i)-1; } } return count; } } |