C++で辞書順最小の等価文字列を求めるアルゴリズム(Union-Find活用)

問題概要

同じ長さの2つの文字列 A と B が与えられ、各位置 i において A[i] と B[i] は「等価な文字」であると定義します。例えば、A = "abc"、B = "cde" の場合、「a」と「c」、「b」と「d」、「c」と「e」がそれぞれ等価であることを意味します。

この等価関係は、一般の同値関係と同じ性質を持ちます。

• 反射律: 'a' = 'a'(任意の文字は自分自身と等価)
• 対称律: 'a' = 'b' ならば 'b' = 'a'
• 推移律: 'a' = 'b' かつ 'b' = 'c' ならば 'a' = 'c'

例えば、上記の A と B の等価性情報をもとにすると、S = "eed"、"acd"、"aab" はすべて互いに等価な文字列であり、その中で辞書順に最も小さいのは "aab" です。本記事の課題は、A と B から得られる等価性情報を利用して、文字列 S の辞書順最小の等価文字列を求めることです。

具体例

入力が A = "parker"、B = "morris"、S = "parser" の場合、出力は "makkek" になります。理由は次のとおりです。A と B の等価性情報に基づいて文字をグループ化すると、[m, p]、[a, o]、[k, r, s]、[e, i] の4つのグループに分かれます。各グループ内の文字は互いに等価であり、置き換えにはグループ内で辞書順に最小の文字を使用します。したがって、"parser" の各文字を対応するグループの最小文字に置き換えると "makkek" が得られます。

解法の考え方: Union-Find(素集合データ構造)

この問題は、Union-Find(Disjoint Set Union)と呼ばれるデータ構造を用いると効率的に解けます。手順は以下のとおりです。

1. サイズ26の配列 parent を作成し、すべて -1 で初期化します(-1 は「未登録」を表します)。
2. getParent(x) メソッドを定義します。文字 x の属するグループの代表を返すメソッドです。parent[x - 'a'] が -1 なら x 自身が代表なので x - 'a' をそのまま返します。それ以外の場合は、再帰的に親を辿りながら経路圧縮を行い、結果を parent[x - 'a'] にキャッシュして返します。
3. union(a, b) メソッドを定義します。まず parentA = getParent(a)、parentB = getParent(b) を求めます。両者が等しければ既に同じグループなので何もしません。異なる場合は、値が小さい方(辞書順で先の文字)を親に設定します。これにより、各グループの代表は常にグループ内で最小の文字になります。
4. メイン処理では、まず parent をサイズ26・全要素 -1 の配列として初期化します。
5. i を 0 から A.size() - 1 まで動かしながら union(A[i], B[i]) を実行し、すべての等価ペアを登録します。
6. 空の文字列 ret を用意し、S の各文字に対して getParent(S[i]) + 'a' を計算して ret に連結します。
7. ret を返します。

ポイントは、統合時に必ず辞書順で小さい方を親に選ぶことです。これにより、最終的に各文字の親を参照すれば、そのグループ内で最小の文字が一意に求まります。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> parent;

    int getParent(char x){
        if(parent[x - 'a'] == -1) return x - 'a';
        return parent[x - 'a'] = getParent('a' + parent[x - 'a']);
    }

    void unionn(char a, char b){
        int parentA = getParent(a);
        int parentB = getParent(b);
        if(parentA == parentB) return;
        if(parentA < parentB){
            parent[parentB] = parentA;
        }else{
            parent[parentA] = parentB;
        }
    }

    string smallestEquivalentString(string A, string B, string S) {
        parent = vector<int>(26, -1);
        for(int i = 0; i < A.size(); i++){
            unionn(A[i], B[i]);
        }
        string ret = "";
        for(int i = 0; i < S.size(); i++){
            ret += getParent(S[i]) + 'a';
        }
        return ret;
    }
};

int main(){
    Solution ob;
    cout << ob.smallestEquivalentString("parker","morris","parser");
}

入力

"parker"
"morris"
"parser"

出力

makkek

計算量について

経路圧縮を用いた Union-Find の各操作はほぼ定数時間で実行できるため、A・B の長さを N、S の長さを M とすると、全体の計算量は O(N + M) に近い形で抑えられます。必要なメモリも固定サイズ26の整数配列のみであり、非常に効率的な解法です。