ডিএনএ সিকোয়েন্সে (A, C, G, T) ১০-অক্ষরের সাবস্ট্রিং যেগুলো একাধিকবার আসে, সেগুলো খুঁজে বের করতে হবে।
উদাহরণ: "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" → ["AAAAACCCCC","CCCCCAAAAA"]।
সমাধানের ধাপসমূহ
- ২-বিট এনকোডিং (A=0, C=1, G=2, T=3) ব্যবহার করে ২০-বিট মাস্ক বানান।
- স্লাইডিং উইন্ডোতে মাস্ক আপডেট করুন (
mask = (mask << 2 | val) & 0xFFFFF)। visitedসেটে দেখা মাস্ক রাখুন,visited2-এ ইতিমধ্যে আউটপুট করা মাস্ক।- নতুন ডুপ্লিকেট পাওয়া গেলে সাবস্ট্রিং যোগ করুন।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<string> v) {
cout << "[";
for (auto& s : v) cout << s << ", ";
cout << "]" << endl;
}
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
vector<string> ret;
int n = s.size();
unordered_set<int> visited, visited2;
unordered_map<char, int> mp = {{'A',0},{'C',1},{'G',2},{'T',3}};
int mask = 0;
for (int i = 0; i < n; i++) {
mask = ((mask << 2) | mp[s[i]]) & 0xFFFFF;
if (i < 9) continue;
if (visited.count(mask) && !visited2.count(mask)) {
ret.push_back(s.substr(i - 9, 10));
visited2.insert(mask);
}
visited.insert(mask);
}
return ret;
}
};
int main() {
Solution ob;
print_vector(ob.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));
}
ইনপুট
"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
আউটপুট
[AAAAACCCCC, CCCCCAAAAA, ]
