首页 > itarticle > algorithm notes: leetcode#409 longest palindrome

algorithm notes: leetcode#409 longest palindrome

admin 11月 12, 2020 0

Problem

Solution

Analysis

Python implementation

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

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 最长回文串