C++-এ জিন মিউটেশন গ্রুপের মোট সংখ্যা বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি জিন স্ট্রিং অ্যারে দেওয়া থাকলে, যেখানে প্রতিটি স্ট্রিং একই দৈর্ঘ্যের এবং শুধু 'A', 'C', 'G', 'T' ক্যারেক্টারগুলো থাকতে পারে। দুই স্ট্রিং যদি শুধু এক ক্যারেক্টার ভিন্ন হয়, তবে তারা একই মিউটেশন গ্রুপে পড়ে। ট্রানজিটিভিটি就是说, যদি s1-s2 এক গ্রুপে এবং s2-s3 এক গ্রুপে থাকে, তবে s1-s3 ও এক গ্রুপে। মোট কতটি মিউটেশন গ্রুপ তৈরি হয় তা বের করতে হবে।

উদাহরণ: genes = ["ACGT", "ACGC", "ACTT", "TTTT", "TGTT"] → ২টি গ্রুপ: ["ACGT","ACGC","ACTT"] এবং ["TTTT","TGTT"]

সমাধানের পদ্ধতি (Union-Find / Disjoint Set Union)

1. প্যারেন্ট ম্যাপ রাখুন প্রতিটি স্ট্রিং-এর জন্য।
2. getPar() ফাংশনে পাথ কম্প্রেশন ব্যবহার করুন।
3. unite() ফাংশনে দুই স্ট্রিং যুন করুন।
4. ok() ফাংশনে দুটি স্ট্রিং শুধু এক ক্যারেক্টার ভিন্ন কিনা চেক করুন।
5. স্ট্রিংগুলো সর্ট করুন এবং সেটে রাখুন।
6. প্রতিটি স্ট্রিং-এর জন্য প্রতিটি পজিশনে 'A','C','G','T' বসিয়ে নতুন স্ট্রিং বানান। যদি সেটে থাকে, তবে ইউন করুন এবং গ্রুপ কাউন্ট কমান।
7. শেষে গ্রুপ সংখ্যা রিটার্ন করুন।

C++ কোড উদাহরণ

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

class Solution {
public:
    map parent;
    
    string getPar(string& a) {
        if (parent[a] == a) return a;
        return parent[a] = getPar(parent[a]);
    }
    
    bool unite(string& a, string& b) {
        string parA = getPar(a);
        string parB = getPar(b);
        if (parA != parB) {
            parent[parA] = parB;
            return true;
        }
        return false;
    }
    
    bool ok(string& a, string& b) {
        int cnt = 0;
        for (int i = 0; i < a.size(); i++)
            cnt += a[i] != b[i];
        return cnt == 1;
    }
    
    int solve(vector v) {
        sort(v.begin(), v.end());
        set s(v.begin(), v.end());
        int ret = v.size();
        
        for (auto& it : v) parent[it] = it;
        
        for (auto& it : v) {
            for (int j = 0; j < it.size(); j++) {
                string temp = it;
                for (char x : {'A', 'C', 'G', 'T'}) {
                    if (x != it[j]) {
                        temp[j] = x;
                        if (s.count(temp)) {
                            if (unite(temp, it)) ret--;
                        }
                    }
                }
            }
        }
        return ret;
    }
};

int main() {
    vector v = {"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"};
    Solution ob;
    cout << ob.solve(v);
    return 0;
}

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

ইনপুট: {"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"}

আউটপুট: 2

জটিলতা

• সময়: O(n × m × 4 × α(n)) — n = স্ট্রিং সংখ্যা, m = স্ট্রিং দৈর্ঘ্য
• স্থান: O(n × m)