[LeetCode] 409. Longest Palindrome [Python] 해시

leetcode.com/problems/longest-palindrome/

Longest Palindrome - LeetCode

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

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

 

이 문제는 주어진 스트링으로 만들 수 있는 가장 긴 팔린드롬의 길이를 찾는 문제이다. Palindrome은  abba나 aba 처럼, 문자열을 반으로 나누어 접었을 때, 미러처럼 딱 맞아떨어지는 것이다. 그 이야기는, 주어진 문자열의 특정 알파벳이 짝수라면 회문구조를 만들 수 있다. 또한, 문제에서 가장 긴 팔린드롬의 길이를 묻는 것이기 때문에, abbcbba처럼 짝수인 알파벳들을 모두 사용하고, 홀수 알파벳을 중간에 넣으면 홀수인 문자열을 만들 수도 있다. 때문에 이 문제는 특정 알파벳이 얼마나 나왔는지 카운트를 해야 되기 때문에 hash table (or hash map)을 사용하는 것이 효과적이다.

---

class Solution:
    def longestPalindrome(self, s: str) -> int:
        lut = collections.Counter(s)
        ans = 0
        odd = False
        for k in lut:
            ans += (lut[k] // 2) * 2
            if lut[k] % 2 != 0: 
                odd = True
        return ans + odd

---

위의 코드와 같이, 해시 테이블을 이용하여 각 캐릭터의 출현 횟수를 기록하고, 출현 숫자를 짝수로 만들어 그 길이만큼 ans에 더해준다. 또한 aba의 경우와 같이 중간에 홀수를 하나 넣을 수 있으므로, 출현 숫자가 홀수인 알파벳이 있는지 체크하여 홀수 알파벳이 있다면 ans값에 1을 더해주면 끝! 이 문제의 runtime complexity는 O(n)이며, space 역시 O(n)이다.