C++で2つの文字列の最長非共通部分列（Longest Uncommon Subsequence I）を求める方法

問題の概要

2つの文字列が与えられたとき、それらの最長非共通部分列（Longest Uncommon Subsequence）の長さを求める問題です。

ここでいう最長非共通部分列とは、一方の文字列の部分列でありながら、もう一方の文字列には一切現れないような、最も長い部分列のことを指します。つまり、この問題では次のような処理を行います。

• 最長非共通部分列の長さを求めて返す
• 最長非共通部分列が存在しない場合は -1 を返す

例えば、入力が "aabbac" と "aabbcc" の場合、出力は 6 になります。

解法のアプローチ

一見すると複雑な動的計画法が必要に思えますが、実は非常にシンプルな考え方で解くことができます。手順は以下の通りです。

• a と b が同じ文字列の場合：どちらかの部分列は必ずもう一方にも現れるため、非共通の部分列は存在しません。よって -1 を返します。
• a と b が異なる文字列の場合：より長い方の文字列全体は、短い方の文字列の部分列にはなり得ません。したがって、a と b のうち長い方の文字数がそのまま答えになります。

C++による実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int findLUSlength(string a, string b) {
        if (a == b)
            return -1;
        else
            return max(a.size(), b.size());
    }
};
main(){
    Solution ob;
    cout << (ob.findLUSlength("aabbac","aabbcc"));
}

入力

"aabbac","aabbcc"

出力

6

コードの解説

この実装のポイントは以下の2点です。

• a == b の比較により、2つの文字列が完全に一致しているかどうかを判定しています。一致していれば非共通部分列は存在しないため -1 を返します。
• 一致していない場合は max(a.size(), b.size()) によって、長い方の文字列の長さをそのまま答えとして返します。これは、長い方の文字列全体が短い方の部分列になることはあり得ないためです。

時間計算量は文字列比較に依存し O(min(|a|, |b|))、空間計算量は O(1) と非常に効率的です。動的計画法などを用意する必要がない、エレガントな解法と言えるでしょう。