Pythonで共通の文字を持たない2つの単語の最大合計長を求めるプログラム

小文字のアルファベットのみで構成された文字列のリスト words が与えられたとき、互いに共通する文字を1つも持たない2つの異なる単語を選び、その長さの合計の最大値を求める問題を考えてみましょう。

例えば、入力が words = ["abcd", "mno", "abdcmno", "amno"] の場合、出力は 7 になります。これは、共通する文字を持たない単語の組み合わせが ["abcd", "mno"] であり、その長さの合計が 4 + 3 = 7 となるためです。

解決のアプローチ

この問題はビットマスク(bitmask)を使うことで効率的に解くことができます。各単語に出現する文字を26ビットの整数として表現し、2つの単語のビットマスク同士のAND演算結果が 0 になれば、「共通の文字を1つも持たない」と判断できます。

具体的な手順は以下の通りです。

• sign() 関数を定義する — 引数として単語 word を受け取ります。
  • value := 0 で初期化します。
  • word 内の各文字 c に対して、value := value OR (2^(ord(c) − ord('a'))) を計算します。
  • value を返します。
• メイン処理では以下を実行します。
  • signature := リスト内の各単語 x に対する sign(x) のリストを作成します。
  • ans := 0 で初期化します。
  • i を 0 から words のサイズ未満まで繰り返し、さらに j を i + 1 から words のサイズ未満まで繰り返します。
  • signature[i] AND signature[j] が 0 と等しい場合、ans := max(ans, len(words[i]) + len(words[j])) を更新します。
• 最後に ans を返します。

それでは、実際の実装を見て理解を深めましょう。

実装例(Pythonコード)

class Solution:
    def sign(self, word):
        value = 0
        for c in word:
            value = value | (1 << (ord(c) - 97))
        return value

    def solve(self, words):
        signature = [self.sign(x) for x in words]
        ans = 0
        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if signature[i] & signature[j] == 0:
                    ans = max(ans, len(words[i]) + len(words[j]))
        return ans

ob = Solution()
words = ["abcd", "mno", "abdcmno", "amno"]
print(ob.solve(words))

入力

["abcd", "mno", "abdcmno", "amno"]

出力

7

計算量について

このアルゴリズムの時間計算量は O(n²)(n は単語の数)です。さらに各単語のシグネチャ計算には単語の長さに比例した処理が必要なため、全体としては O(n² + L)(L は全文字数の合計)となります。空間計算量は O(n) です。ビット演算による比較は非常に高速なため、単語数が多い場合でも実用的な速度で動作します。