C++で解くパーティションラベル問題：文字列を条件付きで最大分割するアルゴリズム

問題概要

小文字のアルファベットのみで構成される文字列 S が与えられます。この文字列を、同じ文字が複数のパートにまたがって現れないという条件を満たしながら、できるだけ多くのパートに分割します。最後に、各パートのサイズを表す整数のリストを返します。

例えば、文字列が「ababcbacadefegdehijhklij」の場合、出力は [9, 7, 8] となります。これは、分割結果が「ababcbaca」「defegde」「hijhklij」の3つのパートになるためです。この分割では、各文字は最大でも1つのパートにしか登場しません。

一方、「ababcbacadefegde」「hijhklij」という2分割は正しくありません。この分割方法では、S をより少ないパート数に分割してしまうからです。

解法のアプローチ（貪欲法）

この問題は、各文字が最後に登場する位置をあらかじめ記録しておくことで、貪欲法（グリーディ法）により効率よく解くことができます。手順は以下のとおりです。

• 文字ごとの最終出現位置を格納するマップ cnt を定義する
• i を 0 から文字列のサイズまで走査し、cnt[s[i]] = i を設定する
• j = 0、start = 0、i = 0 とし、n を文字列のサイズとする
• 結果を格納する配列 ans を定義する
• i < n の間、次の処理を繰り返す
  • j = max(j, cnt[s[i]]) として、現在のパートの終端候補を更新する
  • i == j の場合、ans に i - start + 1 を追加し、start = i + 1 とする（パートが確定）
  • i を 1 増やす
• ans を返す

アルゴリズムのポイント

走査中の変数 j は「これまでに見た文字のうち、最も遠い最終出現位置」を表します。現在位置 i が j と一致した時点で、その区間に含まれるすべての文字が以降のパートには現れないことが保証されるため、そこがパートの区切りとなります。

計算量は、文字列の長さを n とすると、時間計算量 O(n)、空間計算量 O(1)（アルファベットは26種類に固定されるため）と、非常に効率的です。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i < v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]" << endl;
}
class Solution {
public:
   vector<int> partitionLabels(string s) {
      map <char, int> cnt;
      for(int i = 0; i < s.size(); i++) cnt[s[i]] = i;
      int j = 0, start = 0;
      int i = 0;
      int n = s.size();
      vector <int> ans;
      while(i < n){
         j = max(j, cnt[s[i]]);
         if(i == j){
            ans.push_back(i - start + 1);
            start = i + 1;
         }
         i++;
      }
      return ans;
   }
};
main(){
   Solution ob;
   print_vector(ob.partitionLabels("ababcbacadefegdehijhklij"));
}

入力

"ababcbacadefegdehijhklij"

出力

[9, 7, 8]

このように、各文字の最終出現位置を活用した貪欲な走査により、文字列を条件を満たす最大数のパートに分割できます。LeetCodeの「Partition Labels（パーティションラベル）」としても知られる定番問題なので、ぜひマスターしておきましょう。