ความยาวสูงสุดของสตริงต่อกันที่มีตัวอักษรไม่ซ้ำใน C++

ให้อาร์เรย์สตริง arr ต้องการหาความยาวสูงสุดของสตริง s ที่ได้จากการต่อสตริงย่อย (subsequence) ของ arr โดยที่ s ต้องมีตัวอักษรทั้งหมดไม่ซ้ำกัน ตัวอย่าง: ["cha","r","act","ers"] → 6 เพราะได้ "chaers" หรือ "acters"

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

1. สร้างฟังก์ชัน ok(s, t) ตรวจสอบว่าต่อ s และ t แล้วตัวอักษรซ้ำหรือไม่ (ใช้ map นับความถี่)
2. เก็บรายการสตริงที่สร้างได้ใน v เริ่มต้นด้วย ""
3. วนลูปแต่ละสตริงใน arr:
   • วนลูปทุกสตริงที่มีอยู่ใน v (ขนาดก่อนหน้า)
   • ถ้า ok(v[j], arr[i]) เป็นจริง ให้ต่อสตริง ใส่เข้า v และอัปเดตคำตอบสูงสุด
4. คืนค่าความยาวสูงสุด

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

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

class Solution {
public:
    bool ok(string s, string t) {
        unordered_map<char, int> cnt;
        for (char c : s) if (++cnt[c] > 1) return false;
        for (char c : t) if (++cnt[c] > 1) return false;
        return true;
    }
    int maxLength(vector<string>& arr) {
        vector<string> v = {""};
        int ans = 0;
        for (string& str : arr) {
            int n = v.size();
            for (int j = 0; j < n; j++) {
                if (ok(v[j], str)) {
                    string t = v[j] + str;
                    v.push_back(t);
                    ans = max(ans, (int)t.size());
                }
            }
        }
        return ans;
    }
};

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

Input

["cha","r","act","ers"]

Output

6