Repeated DNA Sequences ใน C++: หาลำดับ DNA ยาว 10 ตัวอักษรที่ซ้ำ

โจทย์

กำหนดสตริง DNA ประกอบด้วย A, C, G, T หาลำดับย่อยยาว 10 ตัวอักษรที่เกิดขึ้นมากกว่า 1 ครั้ง

ตัวอย่าง: "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" → ["AAAAACCCCC", "CCCCCAAAAA"]

แนวคิด: Rolling Hash + Bitmask

เข้ารหัส 4 ตัวอักษรเป็น 2 บิต: A=00, C=01, G=10, T=11
ลำดับ 10 ตัว = 20 บิต → ใช้ integer 32-bit เก็บได้ ใช้ bitmask 0xFFFFF (20 บิต)

ขั้นตอน

1. สร้าง map bitVal: A→0, C→1, G→2, T→3
2. mask = 0, สร้าง set visited, visited2
3. ลูป i = 0 ถึง n-1:
   • mask = (mask << 2) | bitVal[s[i]]
   • mask &= 0xFFFFF (เก็บแค่ 20 บิตล่าง)
   • ถ้า i < 9 → continue (ยังไม่ครบ 10 ตัว)
   • ถ้า mask ใน visited แต่อยู่ใน visited2 → เพิ่ม substring ลงผลลัพธ์, ใส่ visited2
   • ใส่ mask ลง visited

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

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

void print_vector(vector<string> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    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> bitVal = {{'A',0},{'C',1},{'G',2},{'T',3}};
        int mask = 0;
        
        for (int i = 0; i < n; i++) {
            mask = ((mask << 2) | bitVal[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"));
    return 0;
}

อินพุต / เอาต์พุต

Input: "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Output: [AAAAACCCCC, CCCCCAAAAA]

ความซับซ้อน

• Time: O(n) - ผ่านสตริง 1 รอบ
• Space: O(n) - เก็บ hash ทั้งหมด