[LeetCode] 1400. Construct K Palindrome Strings (Python)

 

난이도: Medium

 

문제 설명

---

Given a string s and an integer k, return true if you can use all the characters in s to construct k palindrome strings or false otherwise.

 

문제 예제

---

Example 1:

Input: s = "annabelle", k = 2
Output: true
Explanation: You can construct two palindromes using all characters in s.
Some possible constructions "anna" + "elble", "anbna" + "elle", "anellena" + "b"

Example 2:

Input: s = "leetcode", k = 3
Output: false
Explanation: It is impossible to construct 3 palindromes using all the characters of s.

Example 3:

Input: s = "true", k = 4
Output: true
Explanation: The only possible solution is to put each character in a separate string.

 

제한 사항

---

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.
• 1 <= k <= 10^5

 

✏️ Solution(솔루션)

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) == k:
            return True
        if len(s) < k:
            return False
            
        s_counter = Counter(s)

        odd_s = []
        
        for alpha in s_counter:
            if s_counter[alpha] % 2 != 0:
                odd_s.append(alpha)

        if len(odd_s) > k:
            return False
        else:
            return True

 

일단 s의 길이와 k의 값이 같으면 True를 return하고, 또 len(s)가 k보다 작으면 False를 return하도록 하고 코드를 작성했다.

 

처음에는 s의 알파벳을 세가지고 짝수개의 알파벳과 홀수개의 알파벳으로 나누어보았다.

 

그리고 생각난 것이 홀수개의 문자의 개수가 k보다 크다고 한다면 k개의 팰린드롬을 만들 수 없겠다 라는 것이었다.

이를 코드로 구현했고 정답을 맞출 수 있었다.

---

문제: 1400. Construct K Palindrome Strings

 

깃허브: github

algorithmPractice/LeetCode/1502-construct-k-palindrome-strings at main · laewonJeong/algorithmPractice