(Python3) - LeetCode (Medium) : 3517. Smallest Palindromic Rearrangement I

https://leetcode.com/problems/smallest-palindromic-rearrangement-i

Smallest Palindromic Rearrangement I - LeetCode

정렬을 통해 해결한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

📑 dict d, 팰린드롬의 왼편 문자열 left, 가운데 문자열 middle을 선언해준뒤 s의 문자를 순회하며 문자를 key로, 빈도 수를 value로 누적해 세줍니다.

📔 풀이과정

팰린드롬의 특성상 홀수개수인 알파뱃은 가운데에 위치해야합니다. 홀수개수인 알파뱃을 제외하고 짝수빈도를 가진 알파뱃을 양옆에 데칼코마니 형식으로 배치해주면 가장 빠른 사전순의 팰린드롬이 완성됩니다.

📑 key로 정렬된 dict를 순회하며 팰린드롬을 만들어줍니다.

1. left에 특정 알파뱃 ch를 count // 2 만큼 붙여줍니다.

2. 홀수인 알파뱃이 있다면 가운데에 붙일 middle은 ch가 됩니다.

📑 시간 복잡도

O(N): n의 길이의 s에 대해 한번 순회하며 dict에 저장하기 때문입니다.

📑 공간 복잡도

O(k): 26개의 알파뱃에 대한 순회만 진행하기 때문입니다.

📔 정답 출력 | 반환

left + middle + 뒤집은 left를 반환합니다.

---

📕 Code

📔 Python3

class Solution:
    def smallestPalindrome(self, s: str) -> str:
        d = {}

        for ch in s:
            d[ch] = d.get(ch, 0) + 1

        left = ""
        middle = ""

        for ch in sorted(d):
            count = d[ch]

            left += ch * (count // 2)

            if count % 2 == 1:
                middle = ch

        return left + middle + left[::-1]

 

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.