সর্বদীর্ঘ অনকমন সাবসিকোয়েন্স II C++-এ

সমস্যা বিবরণ

স্ট্রিংয়ের একটি লিস্ট দেওয়া আছে। সবচেয়ে লম্বা অকমন সাবসিকোয়েন্সের দৈর্ঘ্য বের করতে হবে। অকমন সাবসিকোয়েন্স বলতে একটি স্ট্রিংয়ের সাবসিকোয়েন্স যেটি অন্য কোনো স্ট্রিংয়ের সাবসিকোয়েন্স নয়। যদি এমন কোনো সাবসিকোয়েন্স না থাকে তবে -1 রিটার্ন করুন।

উদাহরণ

ইনপুট: {"aba", "cdc", "eae"}

আউটপুট: 3 — কারণ প্রতিটি স্ট্রিং অন্যদের সাবসিকোয়েন্স নয়।

অ্যালগরিদম

স্ট্রিংগুলো দৈর্ঘ্য অনুযায়ী ডিসেন্ডিং অর্ডারে সর্ট করুন।
ডুপ্লিকেট স্ট্রিংগুলো খুঁজে বের করুন (যেগুলো একাধিকবার আছে, তারা কখনোই অকমন হতে পারে না)।
সবচেয়ে বড় স্ট্রিং থেকে শুরু করে চেক করুন:
- যদি সেটি ডুপ্লিকেট হয়, স্কিপ করুন।
- যদি এটি প্রথম স্ট্রিং হয় (সবচেয়ে বড়), তবে এর দৈর্ঘ্য রিটার্ন করুন।
- অন্যথায়, এর আগের সব স্ট্রিংয়ের সাথে চেক করুন যে কি এটি তাদের সাবসিকোয়েন্স। যদি কোনো স্ট্রিংয়ের সাবসিকোয়েন্স না হয়, তবে এর দৈর্ঘ্য রিটার্ন করুন।
কোনো স্ট্রিং কাজ না করলে -1 রিটার্ন করুন।

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) {
        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, ret;
        for (auto& s : strs) {
            if (visited.count(s)) ret.insert(s);
            visited.insert(s);
        }
        return ret;
    }

    int findLUSlength(vector<string>& strs) {
        sort(strs.begin(), strs.end(), cmp);
        set<string> duplicates = getDuplicates(strs);
        for (int i = 0; i < strs.size(); i++) {
            if (duplicates.count(strs[i])) continue;
            if (i == 0) return strs[i].size();
            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); // আউটপুট: 3
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট	আউটপুট
`{"aba","cdc","eae"}`	`3`

জটিলতা বিশ্লেষণ

সময় জটিলতা: O(n² × L) — যেখানে n = স্ট্রিং সংখ্যা, L = গড় দৈর্ঘ্য।
স্থান জটিলতা: O(n × L) — সেট সংরক্ষণের জন্য।