C++での一意の文字を含む連結文字列の最大長

文字列arrの配列があるとします。文字列sは、一意の文字を持つarrのサブシーケンスを連結したものです。 sの可能な最大長を見つけます。入力が["cha"、 "r"、 "act"、 "ers"]の場合、出力は6になります。考えられる解決策は、「chaers」と「acters」です。

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

• ok（）という1つのメソッドを作成します。これには、文字列sとtが必要です。これは以下のように動作します
• 1つのマップを作成するx
• 0からsのサイズまでの範囲のiの場合
  • x[s[i]]を1増やします
  • x [s [i]]> 1の場合、falseを返します
• 0からtのサイズまでの範囲のiの場合
  • x[t[i]]を1増やします
  • x [t [i]]> 1の場合、falseを返します
• trueを返す
• 実際の方法は次のようになります-
• vと呼ばれる文字列の配列を作成し、ans：=0、1つの空の文字列をvに挿入します
• 0からarrのサイズまでの範囲のiの場合
  • n：=vのサイズ
  • 0からn–1の範囲のjの場合
    • ok（v [j]、arr [i]）が真の場合、
      • t：=v [j] + arr [i]
      • tをvに挿入
      • ans：=ansの最大値とtのサイズ
• 回答を返す

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool ok(string s, string t){
      map <char, int > x;
      for(int i = 0; i < s.size(); i++){
         x[s[i]]++;
         if(x[s[i]] >1)return false;
      }
      for(int i = 0; i < t.size(); i++){
         x[t[i]]++;
         if(x[t[i]]>1)return false;
      }
      return true;
   }
   int maxLength(vector<string>& arr) {
      vector <string> v;
      int ans = 0;
      v.push_back("");
      for(int i = 0; i < arr.size(); i++){
         int n = v.size();
         for(int j = 0; j < n; j++){
            if(ok(v[j],arr[i])){
               string t = v[j]+arr[i];
               v.push_back(t);
               ans = max(ans,(int)t.size());
            }
         }
      }
      return ans;
   }
};
main(){
   vector<string> v = {"cha","r","act","ers"};
   Solution ob;
   cout << (ob.maxLength(v));
}

入力

["cha","r","act","ers"]

出力

6