C++で解く「最長の非共通部分列 II」― アルゴリズムと実装をわかりやすく解説

文字列のリストが与えられたとき、その中から最長の非共通部分列(Longest Uncommon Subsequence)を見つける問題を考えます。ここでいう非共通部分列とは、リスト内のいずれか1つの文字列の部分列でありながら、他のどの文字列の部分列にもなっていないものを指します。

まず「部分列」とは、元の並びから一部の文字を削除することで得られる列であり、残りの要素の相対的な順序は変更しないものです。たとえば "abc" の部分列には "a"、"ac"、"bc"、"abc" などが含まれます。

本記事では、文字列の配列を受け取り、最長の非共通部分列の長さを返すプログラムをC++で実装します。非共通部分列が存在しない場合は -1 を返します。

たとえば入力が {"aba", "cdc", "eae"} の場合、出力は 3 になります。どの文字列も互いに他の文字列の部分列ではないため、最も長い文字列の長さである 3 が答えとなります。

解法のアプローチ

この問題は、2つの補助関数とソートを組み合わせることで効率よく解けます。

1. isSubsequence(a, b):部分列判定

文字列 b が文字列 a の部分列になっているかどうかを判定します。ポインタ j を用意し、a を先頭から走査しながら a[i] と b[j] が一致するたびに j を進めます。走査終了時に j が b の長さと一致していれば、b は a の部分列であると判断できます。

2. getDuplicates(strs):重複文字列の抽出

配列 strs 内に2回以上出現する文字列を集合として返します。訪問済みを記録するセット visited と、結果を格納するセット ret の2つを用意し、visited に既に存在する文字列を再び見つけたら ret に追加します。

3. メイン処理(findLUSlength)

1. 文字列の配列 strs を長さの降順でソートします。
2. duplicates = getDuplicates(strs) で重複文字列のセットを取得します。
3. i = 0 から strs.size() - 1 までループします。
   • strs[i] が重複文字列であればスキップして次へ進みます。
   • i == 0 の場合(最長かつ一意な文字列)、即座に strs[i].size() を返します。
   • j = 0 から i - 1 までループし、isSubsequence(strs[j], strs[i]) を確認します。すべての j で false になれば(j == i - 1 に到達すれば)、strs[i].size() を返します。途中で true になった場合はループを抜けて次の i へ進みます。
4. すべての候補を調べても見つからなければ -1 を返します。

この手法のポイント

重複する文字列は、同じ内容が別の文字列として存在するため、その部分列が必ず他の文字列の部分列にもなってしまいます。したがって候補から除外する必要があります。また、長さの降順にソートしておくことで、条件を満たした最初の文字列が自動的に「最長」の非共通部分列になります。

C++での実装例

以下に実際のコードを示します。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    static bool cmp(string a, string b){
        return a.size() > b.size();
    }

    int findLUSlength(vector<string>& strs){
        sort(strs.begin(), strs.end(), cmp);
        set<string> duplicates = getDuplicates(strs);
        for (int i = 0; i < strs.size(); i++) {
            if (duplicates.count(strs[i]))
                continue;
            if (i == 0)
                return strs[i].size();
            for (int j = 0; j < i; j++) {
                if (!isSubsequence(strs[j], strs[i])) {
                    if (j == i - 1)
                        return strs[i].size();
                } else {
                    break;
                }
            }
        }
        return -1;
    }

    bool isSubsequence(string a, string b){
        int j = 0;
        for (int i = 0; i < a.size(); i++) {
            if (j < b.size() && a[i] == b[j])
                j++;
        }
        return j == b.size();
    }

    set<string> getDuplicates(vector<string>& strs){
        set<string> visited;
        set<string> ret;
        for (int i = 0; i < strs.size(); i++) {
            if (visited.count(strs[i])) {
                ret.insert(strs[i]);
            }
            visited.insert(strs[i]);
        }
        return ret;
    }
};

int main(){
    Solution ob;
    vector<string> v = {"aba", "cdc", "eae"};
    cout << ob.findLUSlength(v);
    return 0;
}

入力と出力

入力

{"aba", "cdc", "eae"}

出力

3

"aba"、"cdc"、"eae" は互いに部分列の関係にないため、最も長い文字列 "aba" の長さ 3 が答えとして返されます。