leetcode/python/ 409. Longest Palindrome

Description

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.

---

Process

거꾸로 읽어도 똑같은 문자열을 만드는 문제다. 처음에는 같은 문자를 모두 모은 길이가 짝수면 일단 다 정답으로 더해주고 홀수면 그 홀수 길이 중 제일 긴 거 하나만 더하도록 구현했었는데 제출하고 보니까 꼭 그 문자를 다 써야 할 필요가 없었으므로 홀수 역시 한 글자만 제외하면 Palindrome을 만드는 데 유효하다. 그래서 한번 수정했음. 

 

---

Solution

class Solution:
    def longestPalindrome(self, s: str) -> int:
        nums = {}
        for ss in s:
            nums[ss] = 1 + nums.get(ss, 0)
                
        palindrome = 0
        has_odd = False
        for value in nums.values():
            if value & 1: 
                has_odd = True
                palindrome += (value - 1)
            else:
                palindrome += value
        
        return palindrome + 1 if has_odd else palindrome

 

1. s를 순회하면서 딕셔너리에 각 문자가 몇번씩 나타나는지 그 개수를 저장한다.

2. 딕셔너리의 value를 기준으로 순회하면서 문자가 홀수번 나타났으면 -1한 값을, 짝수번 나타났으면 짝수번을 그대로 palindrome에 더해준다.

3. 이때 홀수인 경우 가운데에 한문자를 더 넣을 수 있으므로 홀수가 나타났는지 여부를 체크해주고, return 시 had_odd에 따라 +1을 해준다.

---

Conclusion

아직 생각이 얕다