C++で一意な文字のみを含む連結文字列の最大長を求めるアルゴリズム

文字列の配列 arr が与えられたとします。ここで扱う文字列 s とは、arr の部分列（サブシーケンス）の中から「重複する文字を一切含まないもの」を選び、それらを連結して作られる文字列のことです。この問題の目的は、そのような s として実現できる最大の長さを求めることです。

例えば、入力が ["cha", "r", "act", "ers"] の場合、出力は 6 になります。このとき条件を満たす解としては "chaers" や "acters" が挙げられます。

解法のアプローチ

この問題を解くために、以下の手順に従って進めます。

• まず、2つの文字列 s と t を受け取るメソッド ok() を作成します。このメソッドは以下のように動作します。
• マップ x を用意します。
• i を 0 から s のサイズまでループさせます。
  • x[s[i]] を1増やします。
  • x[s[i]] が1より大きくなった場合、文字が重複しているため false を返します。
• i を 0 から t のサイズまでループさせます。
  • x[t[i]] を1増やします。
  • x[t[i]] が1より大きくなった場合は false を返します。
• すべてのチェックを通過したら true を返します。これにより、s と t を連結しても文字の重複が発生しないかを判定できます。

続いて、本体となるメソッドは以下のような流れになります。

• 文字列の配列 v を用意し、答えを格納する変数 ans := 0 で初期化します。さらに、空文字列を v に挿入しておきます。
• i を 0 から arr のサイズまでループさせます。
  • n := v の現在のサイズ
  • j を 0 から n - 1 までループさせます。
    • ok(v[j], arr[i]) が true を返した場合：
      • t := v[j] + arr[i] として新しい連結文字列を作成
      • t を v に追加
      • ans := max(ans, t のサイズ) で最大長を更新
• 最終的に ans を返します。

この手法では、既に見つかったすべての有効な連結候補を v に保持し、各文字列が新しく追加できるかどうかを順番に検証することで、組み合わせを網羅的に探索しています。

それでは、理解を深めるために以下の実装例を見てみましょう。

実装例

#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