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>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
}