C++でK回文文字列を作成する

文字列sと数値kがあるとします。 sのすべての文字を使用して、k個の空でない回文文字列を作成する必要があります。したがって、ここでは、s内のすべての文字を使用してk回文文字列を作成できるかどうかを確認する必要があります。

したがって、入力が「true」のようである場合、k =4の場合、出力はTrueになります。これは、各文字を別々の文字列に入れることが唯一の解決策であるためです。

これを解決するには、次の手順に従います-

• n：=sのサイズ

• n

  • falseを返す

• nがkと同じ場合、-

  • trueを返す

• 1つのマップを定義する

• sの各文字cについて

  • （m [c]を1増やします）

• 奇数：=0

• キーと値のペアごとに、m −

  • 奇数：=奇数+（その値AND 1）

• 奇数<=kの場合はtrueを返し、それ以外の場合はfalse

例

理解を深めるために、次の実装を見てみましょう-

#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));
}

入力

"true"

出力

1