Độ dài lớn nhất chuỗi nối có ký tự duy nhất trong C++

Mô tả bài toán

Cho mảng chuỗi arr. Tìm độ dài lớn nhất của chuỗi được nối từ một dãy con của arr sao cho tất cả ký tự trong chuỗi kết quả đều khác nhau.

Ví dụ: ["cha","r","act","ers"] → kết quả 6 (chuỗi "chaers" hoặc "acters").

Giải thuật Quay lui + Bitmask

Vì chỉ có 26 chữ cái thường, dùng bitmask 32-bit biểu diễn tập ký tự.

1. Lọc trước: bỏ các chuỗi có ký tự trùng lặp nội bộ.
2. Chuyển mỗi chuỗi thành bitmask.
3. Duyệt tất cả tập con (backtracking hoặc DP trên bitmask): thử nối chuỗi hiện tại nếu (mask & cur_mask) == 0.
4. Cập nhật độ dài lớn nhất.

Cài đặt C++ (Tối ưu Bitmask)

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

class Solution {
public:
    int maxLength(vector<string>& arr) {
        vector<int> masks;
        for (auto& s : arr) {
            int mask = 0, ok = 1;
            for (char c : s) {
                int bit = c - 'a';
                if (mask & (1 << bit)) { ok = 0; break; }
                mask |= 1 << bit;
            }
            if (ok) masks.push_back(mask);
        }
        int ans = 0;
        function<void(int,int)> dfs = [&](int idx, int cur) {
            ans = max(ans, __builtin_popcount(cur));
            for (int i = idx; i < masks.size(); i++) {
                if ((cur & masks[i]) == 0) dfs(i+1, cur | masks[i]);
            }
        };
        dfs(0, 0);
        return ans;
    }
};

int main() {
    vector<string> v = {"cha","r","act","ers"};
    Solution ob;
    cout << ob.maxLength(v); // 6
    return 0;
}

Độ phức tạp

• Thời gian: O(2^m) với m = số chuỗi hợp lệ (≤ 16 trong thực tế).
• Không gian: O(m) cho đệ quy.