Problem
Solution
Analysis
Python implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|
class : def longestPalindrome(self, s): """ :type s: str :rtype: int """ counter = dict() has_odd = False ans = 0 for c in s: counter[c] = counter.get(c, 0)+1 for n in counter.values(): if n % 2: has_odd = True ans += (n // 2) * 2 return ans+1 if has_odd else ans
|
Java implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
|
class { public int longestPalindrome(String s) { Map<Character, Integer> counter = new HashMap<>(); boolean hasOdd = false; int ans = 0; for(char c : s.toCharArray()){ counter.put(c, counter.getOrDefault(c,0)+1); } for(int n : counter.values()){ if(n%2!=0){ hasOdd = true; } ans += (n/2)*2; } return hasOdd ? ans+1 : ans; } }
|
Time complexity
O(N).
Space complexity
O(1).
Link
409. Longest Palindrome
(中文版) 算法笔记: 力扣#409 最长回文串
近期评论