【C++】部分列の連結で文字列を形成する最短の方法 ― 最小回数を求めるアルゴリズム

問題概要

文字列の部分列（subsequence）とは、元の文字列からいくつかの文字を削除することで得られる文字列です（削除なしでも構いません）。

source と target の2つの文字列が与えられたとき、target を作るために必要な source の部分列の最小個数を求めます。どうしても作れない場合は -1 を返します。

たとえば、source = "abc"、target = "abcbc" の場合、出力は 2 になります。
これは「abc」という部分列で最初の3文字をカバーし、続けて「bc」という部分列で残りの2文字をカバーできるためです。

アプローチ：貪欲法＋二分探索

この問題は、target の各文字を source 内のできるだけ先頭に近い位置から順番に消費していく貪欲法で効率よく解けます。具体的には以下の手順に従います。

ステップ1：実行可能性のチェック

• s と t を引数にとる関数 possible を定義します。

• マップ m を作成し、s に含まれる各文字 c に対して m[c] := 1 とマークします。

• t 内のどれか一つの文字でも m[c] が 0 なら false を返します（その時点で -1 が確定）。

• すべて含まれていれば true を返します。

ステップ2：位置情報の前処理

• ssz := s のサイズ、tsz := t のサイズとします。

• 「キー＝文字型、値＝整数配列型」のマップ m を作成します。

• i を 0 から ssz−1 までループし、各文字の出現位置 i を m[s[i]] に挿入していきます。

ステップ3：本体ループ

• pre := -1（直前に使った位置）、ret := 1（部分列のカウント）で初期化します。

• i を 0 から tsz−1 までループします。

  • t[i] が m に存在しなければ -1 を返します。

  • v := m[t[i]]（その文字が出現する位置のリスト）を取得します。

  • upper_bound を使い、pre より大きい位置を二分探索で見つけます。

  • 見つからなかった場合（リスト末尾に到達）：
    → 現在の部分列ではこれ以上進めないため、ret を 1 増やして新しい部分列を開始し、pre := v[0] とします。

  • 見つかった場合は pre := *it として続けます。

• 最後に ret を返します。

ポイントは、各文字の出現位置をあらかじめソート済みリストとして保持しておくことで、upper_bound による二分探索が O(log n) で動作し、全体の計算量を O(|s| + |t| log |s|) に抑えられる点です。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool possible(string s, string t){
      map <char, int> m;
      for(int i = 0; i < s.size(); i++){
         m[s[i]] = 1;
      }
      for(int i = 0; i < t.size(); i++){
         if(!m[t[i]])return false;
      }
      return true;
   }
   int shortestWay(string s, string t) {
      int ssz = s.size();
      int tsz = t.size();
      map <char, vector <int> > m;
      for(int i = 0; i < ssz; i++){
         m[s[i]].push_back(i);
      }
      int pre = -1;
      int ret = 1;
      for(int i = 0; i < tsz; i++){
         if(!m.count(t[i]))return -1;
         vector <int>& v = m[t[i]];
         vector <int> :: iterator it = upper_bound(v.begin(),
         v.end(), pre);
         if(it == v.end()){
            ret++;
            pre = v[0];
         }else{
            pre = *it;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.shortestWay("abc", "abcbc"));
}

入力

"abc"
"abcbc"

出力

2

まとめ

このアルゴリズムは、各文字の出現位置を前計算しておき、二分探索で「次に使える最も近い位置」を高速に探すことで、部分列の連結回数を貪欲に最小化します。文字種が多い・文字列が長いケースでも効率的に動作するため、競技プログラミングや実務のコーディング面接でも応用範囲の広い手法です。