Pythonで重複文字のない連結文字列の最大の長さを求めるプログラム

問題概要

文字列のリスト words が与えられます。ここからいくつかの単語(部分列)を選んで連結し、「すべての文字が一意(重複なし)」となる文字列を作ることを考えます。そのような連結の中で、最も長くなるものの長さを求めるのがこの問題の目的です。

例えば、words = ["xyz", "xyw", "wab", "cde"] の場合、答えは 9 になります。「xyz」「wab」「cde」の3つを選んで連結すると「xyzwabcde」となり、x・y・z・w・a・b・c・d・e の9文字がすべて異なるためです。

アプローチ:再帰による全探索

この問題は、各単語に対して「連結に使う / 使わない」の2択を順番に試していく再帰的な探索(バックトラッキング)で解くことができます。手順は次の通りです。

• 答えを格納する変数 ans を 0 で初期化します。
• 再帰関数 recur(i, cur) を定義します。i は現在見ている単語のインデックス、cur はこれまでに連結した文字列です。
• i が単語の総数と等しくなったら、ans と len(cur) の大きい方で ans を更新して終了します。
• まず現在の単語を「使わない」ケースとして recur(i + 1, cur) を呼び出します。
• words[i] 自体に重複文字がなく、かつ cur + words[i] にも重複がない場合は、「使う」ケースとして recur(i + 1, cur + words[i]) も呼び出します。
• メイン処理から recur() を呼び出し、最後に ans を返します。

Pythonでの実装例

class Solution:
    def solve(self, words):
        ans = 0

        def is_all_unique(s):
            return len(set(s)) == len(s)

        def recur(i=0, cur=""):
            nonlocal ans
            if i == len(words):
                ans = max(ans, len(cur))
                return

            # 現在の単語を使わない場合
            recur(i + 1, cur)

            # 重複がなければ、現在の単語を使う場合も試す
            if is_all_unique(words[i]) and is_all_unique(cur + words[i]):
                recur(i + 1, cur + words[i])

        recur()
        return ans

ob = Solution()
words = ["xyz", "xyw", "wab", "cde"]
print(ob.solve(words))

入力

["xyz", "xyw", "wab", "cde"]

出力

9

ポイント解説

is_all_unique() 関数では、文字列を set に変換したときの要素数が元の文字数と一致するかどうかで、重複の有無を判定しています。セットに変換すると重複が自動的に取り除かれるため、長さが変わらなければ「すべての文字が一意」であると分かります。

計算量の面では、各単語ごとに「使う / 使わない」の2通りの分岐が生じるため、最悪の場合は O(2^n) の探索になります。ただし、重複が発生した時点でその分岐を打ち切る(枝刈りする)ことで、無駄な探索を大幅に削減できます。さらに高速化したい場合は、各単語の文字集合をビットマスク(整数)で表現し、ビット演算の AND で重複を判定する手法が有効です。