[2024] day 157. leetcode 409. Longest Palindrome

gunny·2024년 6월 4일

leetcode 409. Longest Palindrome leetcode 409. Longest Palindrome python

코딩테스트

목록 보기

471/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 6월 4일 (화)
Leetcode daily problem

https://leetcode.com/problems/longest-palindrome/

https://leetcode.com/problems/longest-palindrome/?envType=daily-question&envId=2024-06-04

Problem

소문자 또는 대문자로 구성된 문자열 s가 주어지면 해당 문자로 만들 수 있는 가장 긴 펠린드롬(회문)의 길이를 반환한다.
문자는 대소문자를 구분한다. 예를 들어 "Aa"는 회문으로 간주되지 않는다.

Solution

Greedy Way

팰린드롬을 만들기 위해서는 문자 쌍이 필요하다.
이를 위해서 각 문자의 빈도를 세는데, 여기서 짝수 개수를 가진 문자는 모두 팰린드롬에 사용될 수 있다.
홀수 개수를 가진 문자는 그 중 한 개를 제외하고 모두 쌍을 이뤄 사용할 수 있게 된다.

따라서 팰린드롬의 길이를 계산하는 방법은

문자열 s에서 각 문자의 빈도를 업데이트
빈도 수가 짝수인 문자는 모두 사용
빈도 수가 홀수인 문자는 최대 한 문자까지 홀수로 사용할 수 있고 나머지는 짝수 개로 사용함
결과적으로 홀수 개 문자가 있다면 팰린드롬의 길이에 1을 더해줌(팰린드롬의 중앙에 하나의 홀수 문자를 배치함).

Code

class Solution:
    def longestPalindrome(self, s: str) -> int:
        freq_map = {}
        ans = 0
        
        for c in s : 
            freq_map[c] = freq_map.get(c,0)+1
            
        odd_op = False 
        for cnt in freq_map.values():
            if cnt %2==0:
                ans += cnt
                
            else:
                ans += cnt-1
                odd_op = True
                
        if odd_op:
            return ans +1
        
        return ans