# LeetCode 1400. Construct K Palindrome Strings

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

## 題目大意

判斷字串 `s` 內的英文字母能否拼出 `k` 個迴文字串

## 思考

想想看怎樣的 input `s` 需要 return `false`？

最簡單的情況就是 `s` 的長度根本就沒超過 `k`

另一種情況是本題關鍵：

若 `s` 中存在字母 `c` 其頻率 $\mathrm{freq}_c \gt k$ 且 $\mathrm{freq}_c$ 為奇數
則 `s` 內的字母肯定無法剛好拼出 `k` 個迴文字串

C++ 參考解答：

class Solution
{
public:
    bool canConstruct(string s, int k)
    {
        if (s.length() < k)
            return false;

        bitset<26> odd;

        for (const char c : s)
        {
            odd.flip(c - 'a');
        }

        return odd.count() <= k;
    }
};

Go 參考解答：

func canConstruct(s string, k int) bool {
	if len(s) < k {
		return false
	}

	cnt := [26]int{}

	for _, c := range s {
		cnt[c-'a']++
	}

	odd := 0
	for _, freq := range cnt {
		if freq&1 == 1 {
			odd++
		}
	}

	return odd <= k
}