1400. Construct K Palindrome Strings

#Problem

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.

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

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.

Constraints:

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

#Test Cases

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:

import pytest

from solution import Solution


@pytest.mark.parametrize('s, k, expected', [
    ("annabelle", 2, True),
    ("leetcode", 3, False),
    ("true", 4, True),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, s, k, expected):
    assert sol.canConstruct(s, k) == expected

#Thoughts

设 s 的长度为 n，首先如果 n < k 就肯定不行。

然后看 s 中个数为奇数的字符，设有 m 个（0 ≤ m ≤ n），因为每个回文最多只能有一个字符的个数是奇数（最中间的字符），所以如果 m > k 就肯定不行。

把那 m 个奇数个数的字符，各取一个出来，分别先构成一个单字符回文，一共 m 个。然后看 k - m 的奇偶性，如果是偶数则任取 (k - m) / 2 对字符，打散，每个字符构成一个独立的回文。如果是奇数，则取 floor((k - m) / 2) 对字符，各自构成一个单字符回文，再任取一对字符构成一个长度为二的回文。这样 s 中剩下的字符一定是成对的，可以直接都给某一个已经构造出来的回文，构成一个长的回文。

#Code

from collections import defaultdict


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

        parity: dict[str, int] = defaultdict(int) # {c: 1 if c is odd, 0 if even}
        for c in s:
            parity[c] = 1 - parity[c]

        return sum(parity.values()) <= k