C++で解く単語の長さの最大積問題 ― ビットマスクによる効率的な実装

問題概要

文字列の配列 words が与えられたとき、互いに共通の文字を1つも持たない2つの単語 word[i] と word[j] を選び、length(word[i]) × length(word[j]) の最大値を求めます。各単語には小文字の英字のみが含まれるものとします。条件を満たすペアが存在しない場合は 0 を返します。

例えば、入力が ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"] の場合、出力は 16 になります。「abcw」と「xtfn」は共通の文字を持たず、長さの積が 4 × 4 = 16 となるためです。

解法のアプローチ：ビットマスクで文字集合を表現する

この問題を効率的に解くポイントは、各単語に含まれる文字の集合を26ビットの整数（ビットマスク）として表現することです。英小文字は26種類しかないため、各文字に1ビットを割り当てれば、単語の文字情報を1つの整数に圧縮できます。

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

1. 各単語 s について、key = 0 から始めて、含まれる各文字 c に対し key = key OR 2^(c − 'a') を計算します。これで s の文字集合を表すビットマスクが得られます。
2. 作成したビットマスクをマップ m に、単語のインデックス i をキーとして格納します（m[i] = key）。
3. すべての単語ペア (i, j)（i < j）について、m[i] AND m[j] == 0 であれば2つの単語は共通文字を持ちません。このとき length(word[i]) × length(word[j]) を計算し、現在の最大値 ret より大きければ更新します。
4. 最後に ret を返します。

AND演算によって「2つの単語が共通の文字を持つかどうか」を定数時間で判定できるのが、この手法の大きな強みです。

補足：getRev() 関数について

サンプルコードには getRev() という関数が含まれています。これは与えられたビットマスク x の補集合（含まれていない文字の集合）を求める関数ですが、maxProduct() の本質的なロジックでは呼び出されていません。ビット操作の理解のための参考として掲載しています。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int getRev(int x){
        int ret = 0;
        for(int i = 0; i <= 25 ; i++){
            if(!((x >> i) & 1)){
                ret |= (1 << i);
            }
        }
        return ret;
    }
    int maxProduct(vector<string>& words) {
        unordered_map <int, int> m;
        int n = words.size();
        for(int i = 0; i < n; i++){
            string s = words[i];
            int key = 0;
            for(int j = 0; j < s.size(); j++){
                key |= 1 << (s[j] - 'a');
            }
            m[i] = key;
        }
        int ret = 0;
        for(int i = 0; i < words.size(); i++){
            for(int j = i + 1; j < words.size(); j++){
                if((m[i] & m[j]) == 0){
                    ret = max(ret, (int)words[i].size() * (int)words[j].size());
                }
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<string> v = {"abcw","baz","foo","bar","xtfn","abcdef"};
    cout << (ob.maxProduct(v));
}

入力

["abcw","baz","foo","bar","xtfn","abcdef"]

出力

16

計算量の評価

・時間計算量：O(n² + L)。ここで n は単語数、L は全単語の文字数の合計です。ビットマスクの構築に O(L)、すべてのペアの判定に O(n²) が必要です。
・空間計算量：O(n)。各単語のビットマスクを保存するためのマップが必要です。

各ペアについて文字を1つずつ比較する素朴な方法と比べると、ビットマスク化によって共通文字の判定コストが大幅に削減され、より多くのデータに対しても実用的な速度で動作します。