Construct K Palindrome Strings in C++

Suppose we have a string s and a number k. We have to construct k non-empty palindrome strings using all the characters in s. So here we have to check whether we can use all the characters in s to construct k palindrome strings or not.

So, if the input is like "true", k = 4, then the output will be True, as the only possible solution is to put each character in a separate string.

To solve this, we will follow these steps −

• n := size of s

• if n < k, then −

  • return false

• if n is same as k, then −

  • return true

• Define one map

• for each character c in s

  • (increase m[c] by 1)

• odd := 0

• for each key-value pair it in m −

  • odd := odd + (value of it AND 1)

• return true when odd <= k, otherwise false

Example 

Let us see the following implementation to get a better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution { public:    bool canConstruct(string s, int k) {       int n = s.size();       if (n < k)          return false;       if (n == k)          return true;       map<char, int> m;       for (char c : s)          m[c]++;       int odd = 0;       for (auto& it : m) {          odd += (it.second & 1);       }       return odd <= k;    } }; main(){    Solution ob;    cout << (ob.canConstruct("true",4)); }

Input

"true"

Output

1