# 1400.construct-k-palindrome-strings

## Statement

• Difficulty: Medium
• Tag: `贪心` `哈希表` `字符串` `计数`

``````输入：s = "annabelle", k = 2

``````

``````输入：s = "leetcode", k = 3

``````

``````输入：s = "true", k = 4

``````

``````输入：s = "yzyzyzyzyzyzyzy", k = 2

``````

``````输入：s = "cr", k = 7

``````

• `1 <= s.length <= 10^5`
• `s` 中所有字符都是小写英文字母。
• `1 <= k <= 10^5`

• Link: Construct K Palindrome Strings
• Difficulty: Medium
• Tag: `Greedy` `Hash Table` `String` `Counting`

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.
``````

Constraints:

• `1 <= s.length <= 105`
• `s` consists of lowercase English letters.
• `1 <= k <= 105`

## Solution

``````#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define SZ(x) int((x).size())
#define endl "\n"
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}

int cnt[30];

class Solution {
public:
bool canConstruct(string s, int k) {
int len = SZ(s);
memset(cnt, 0, sizeof cnt);
for (auto &c : s) ++cnt[c - 'a'];
if (len < k)
return false;
int t = 0;
for (int i = 0; i < 26; ++i) t += cnt[i] % 2;
return t <= k;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````