Dãy con không chung dài nhất II trong C++

Giới thiệu

Cho danh sách các chuỗi. Tìm độ dài của dãy con (subsequence) dài nhất của một chuỗi nào đó, mà dãy con đó KHÔNG là dãy con của bất kỳ chuỗi nào khác trong danh sách. Nếu không tồn tại, trả về -1.

Dãy con: xóa bớt ký tự nhưng giữ nguyên thứ tự.

Ý tưởng

• Sắp xếp các chuỗi theo độ dài giảm dần.
• Loại bỏ các chuỗi trùng lặp (nếu chuỗi xuất hiện ≥2 lần thì không thể là "uncommon").
• Duyệt từ chuỗi dài nhất. Với chuỗi s[i], kiểm tra xem nó có phải dãy con của bất kỳ chuỗi nào dài hơn hoặc bằng nó (đã xét trước) không. Nếu không phải dãy con của chuỗi nào → đó là đáp án.

Cài đặt C++

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

class Solution {
public:
    static bool cmp(string a, string b) { return a.size() > b.size(); }

    bool isSubsequence(string a, string b) {
        // kiểm tra b có phải dãy con của a không
        int j = 0;
        for (int i = 0; i < a.size() && j < b.size(); i++)
            if (a[i] == b[j]) j++;
        return j == b.size();
    }

    set<string> getDuplicates(vector<string>& strs) {
        set<string> visited, dup;
        for (auto& s : strs) {
            if (visited.count(s)) dup.insert(s);
            visited.insert(s);
        }
        return dup;
    }

    int findLUSlength(vector<string>& strs) {
        sort(strs.begin(), strs.end(), cmp);
        set<string> dup = getDuplicates(strs);
        for (int i = 0; i < strs.size(); i++) {
            if (dup.count(strs[i])) continue;
            bool ok = true;
            for (int j = 0; j < i; j++) {
                if (isSubsequence(strs[j], strs[i])) { ok = false; break; }
            }
            if (ok) return strs[i].size();
        }
        return -1;
    }
};

int main() {
    Solution ob;
    vector<string> v = {"aba", "cdc", "eae"};
    cout << ob.findLUSlength(v); // Output: 3
    return 0;
}

Phân tích

• Thời gian: O(n² * L) với n = số chuỗi, L = độ dài trung bình.
• Không gian: O(n * L) để lưu chuỗi.

Lưu ý: Sắp xếp giảm dần độ dài đảm bảo chuỗi dài nhất được xét trước, giúp dừng sớm.