(Python3) - LeetCode (Medium) : 1400. Construct K Palindrome Strings

https://leetcode.com/problems/construct-k-palindrome-strings/description

palindrome조건을 적용해본 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

홀수 빈도 수를 가진 odd_char_num를 선언 후 0으로 초기화합니다. 각 알파뱃별 빈도수를 저장할 alpha_map을 선언 후 s에 대해 for loop를 수행하며 빈도수를 저장해줍니다.

📔 풀이과정

1. 최소 palindrome은 하나의 문자이므로 s의 길이가 k미만이면 k개를 사용해 s를 만들 수 없으므로 False를 반환합니다.

 

2. palindrome의 조건은 홀수개인 문자가 1개거나 0개일 때 나머지 문자들은 모두 짝수여야 합니다. k개의 palindrome으로 s를 만들어야 하기 때문에 홀수개인 문자들로 k개를 구성하면 나머지 짝수개의 문자들로 펠린드롬을 어떻게든 만들 수 있기 때문에 반대로 홀수 빈도수를 가진 문자들의 개수가 k개를 초과한다면 만들 수 없게 된다는 결론을 얻을 수 있습니다. 따라서 이 경우도 False를 반환합니다.

📔 정답 출력 | 반환

나머지 경우에는 k개의 palindrome으로 s를 만들 수 있으므로 True를 반환합니다.

---

📕 Code

📔 Python3

from collections import defaultdict, Counter

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k:
            return False
        odd_char_num = 0
        alpha_map = defaultdict(int)
        for char in s:
            alpha_map[char] += 1
        for char, freq in alpha_map.items():
            if freq % 2 == 1:
                odd_char_num += 1
        if odd_char_num > k:
            return False
        return True

---

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