Longest Uncommon Subsequence II ใน C++

ปัญหา: Longest Uncommon Subsequence II

กำหนดรายการสตริง หา ความยาวของ subsequence ที่ไม่ซ้ำ (uncommon) ที่ยาวที่สุด

Uncommon subsequence = subsequence ของสตริงหนึ่งที่ ไม่ใช่ subsequence ของสตริงอื่นใดในรายการ

นิยาม Subsequence

ลำดับที่ได้จากการลบตัวอักษรบางส่วน (อาจไม่ลบเลย) โดยไม่เปลี่ยนลำดับตัวอักษรที่เหลือ

ตัวอย่าง

Input: ["aba", "cdc", "eae"]

Output: 3

เพราะแต่ละสตริงยาว 3 และไม่ใช่ subsequence ของอีกสองตัว

แนวทางแก้ปัญหา

ข้อสังเกตสำคัญ

• ถ้าสตริง s ไม่ใช่ subsequence ของสตริงอื่นใด → s เองคือ uncommon subsequence ที่ยาวที่สุดของมันเอง
• ดังนั้น ตรวจสอบจากสตริงที่ ยาวที่สุดก่อน – ถ้าพบว่ามันไม่ใช่ subsequence ของอันอื่น → คืนความยาวทันที
• สตริงซ้ำ (duplicate) ไม่สามารถเป็น uncommon ได้ เพราะมันเป็น subsequence ของตัวเองอีกตัว

ขั้นตอน

1. เรียงสตริงตามความยาว มากไปน้อย
2. หาสตริงซ้ำ (duplicates) – เก็บใน set
3. วนลูปสตริงแต่ละตัว (จากยาวสุด):
   • ถ้าอยู่ใน duplicates → ข้าม
   • ถ้าเป็นตัวแรก (ยาวสุด) และไม่ซ้ำ → คืนความยาวทันที
   • ตรวจสอบว่าเป็น subsequence ของสตริงก่อนหน้า (ที่ยาวกว่าหรือเท่ากัน) ไหม
     • ถ้า ไม่ใช่ subsequence ของ ทุกตัว ก่อนหน้า → คืนความยาว
     • ถ้าเป็น subsequence ของตัวไหนตัวหนึ่ง → ข้าม (เพราะสตริงก่อนหน้ายาวกว่าหรือเท่ากัน)
4. ไม่พบ → คืน -1

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

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

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

    bool isSubsequence(const string& a, const string& b) {
        // b เป็น subsequence ของ a หรือไม่
        int j = 0;
        for (int i = 0; i < a.size() && j < b.size(); i++)
            if (a[i] == b[j]) j++;
        return j == b.size();
    }

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

    int findLUSlength(vector<string>& strs) {
        sort(strs.begin(), strs.end(), cmpLen);
        auto duplicates = getDuplicates(strs);

        for (int i = 0; i < strs.size(); i++) {
            if (duplicates.count(strs[i])) continue;
            if (i == 0) return strs[i].size(); // longest unique

            bool isSub = false;
            for (int j = 0; j < i; j++) {
                if (isSubsequence(strs[j], strs[i])) {
                    isSub = true;
                    break;
                }
            }
            if (!isSub) return strs[i].size();
        }
        return -1;
    }
};

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

ความซับซ้อน

• เวลา: O(n² × L) โดย n = จำนวนสตริง, L = ความยาวเฉลี่ย (จากการตรวจ subsequence)
• พื้นที่: O(n × L) – เก็บสตริงและ set

ข้อสังเกต

• การเรียงจากยาวไปสั้น ช่วย prune ได้เร็ว – พบคำตอบเร็วขึ้น
• Duplicate handling สำคัญ – สตริงซ้ำไม่เคยเป็นคำตอบ
• ฟังก์ชัน isSubsequence ใช้ two-pointer O(L)