Tích lớn nhất độ dài 2 từ không chung ký tự trong C++

Mô tả bài toán

Cho mảng chuỗi words (chỉ chữ thường). Tìm max len(words[i]) * len(words[j]) sao cho 2 từ không có ký tự chung. Trả về 0 nếu không có cặp nào.

Ví dụ: ["abcw","baz","foo","bar","xtfn","abcdef"] → 16 ("abcw" và "xtfn", 4×4=16).

Giải thuật Bitmask

1. Mỗi từ → bitmask 26 bit: bit i = 1 nếu có chữ 'a'+i.
2. Hai từ không chung ký tự ⇔ (mask[i] & mask[j]) == 0.
3. Duyệt tất cả cặp (i,j), cập nhật max tích độ dài.

Cài đặt C++

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

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

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

Độ phức tạp

• Thời gian: O(n^2 + L) (L = tổng độ dài từ).
• Không gian: O(n) cho mảng mask.