ผลคูณความยาวคำสูงสุดที่ไม่มีตัวอักษรร่วมใน C++

ให้อาร์เรย์สตริง words หา max(len(word[i]) * len(word[j])) โดยที่ word[i] และ word[j] ไม่มีตัวอักษรร่วมกัน (lowercase เท่านั้น) หาไม่ได้คืน 0

ตัวอย่าง: ["abcw","baz","foo","bar","xtfn","abcdef"] → 16 (abcw และ xtfn)

ขั้นตอนการแก้ปัญหา (Bitmask)

1. แปลงแต่ละคำเป็น bitmask 26 บิต: บิต k = 1 ถ้ามีตัวอักษร 'a'+k
2. เก็บ mask ใน map m[i]
3. วนคู่ (i,j) ทุกคู่: ถ้า (m[i] & m[j]) == 0 → ไม่มีตัวอักษรร่วม อัปเดตคำตอบด้วย len(i) * len(j)
4. คืนค่าสูงสุด

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int maxProduct(vector<string>& words) {
        unordered_map<int, int> mask;
        int n = words.size();
        for (int i = 0; i < n; i++) {
            int key = 0;
            for (char c : words[i]) key |= 1 << (c - 'a');
            mask[i] = key;
        }
        int ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((mask[i] & mask[j]) == 0) {
                    ret = max(ret, (int)words[i].size() * (int)words[j].size());
                }
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<string> v = {"abcw","baz","foo","bar","xtfn","abcdef"};
    cout << ob.maxProduct(v);
}

Input

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

Output

16