019 — Repeated DNA Sequences¶

Source¶

Original source: Classic seen-set-of-windows / rolling-hash teaser exercise
Platform: LeetCode — https://leetcode.com/problems/repeated-dna-sequences/
Topic: hash set (sliding-window keys)
Difficulty: Medium
Pattern: seen-set of windows / rolling-hash teaser
Basic idea inherited from: seen-set + substring keys — প্রতিটা window-কে একটা key বানিয়ে "আগে দেখেছি?" জিজ্ঞেস করা

1. Problem in simple words¶

একটা DNA string s দেওয়া আছে, যেটায় শুধু চারটা অক্ষর — 'A', 'C', 'G', 'T'। যেসব 10-অক্ষরের পরপর টুকরো (substring) string-টায় একাধিকবার আসে, সেগুলোর তালিকা ফেরত দিতে হবে (প্রতিটা একবার করে)।

s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGGG"
"AAAAACCCCC" দুবার আসে, "CCCCCAAAAA" দুবার আসে
উত্তর: ["AAAAACCCCC", "CCCCCAAAAA"]

2. Which basic idea does this inherit from?¶

এটা seen-set (Pattern 4)-এর সরাসরি সম্প্রসারণ — "এটা কি আগে দেখেছি?" O(1)-এ। নতুনত্ব হলো: এখন element একটা একক সংখ্যা নয়, একটা গোটা 10-অক্ষরের window। প্রতিটা window-কে একটা key (substring নিজেই, বা তার hash) ভেবে set-এ ফেলি। এখান থেকেই rolling hash (Pattern 7)-এর দরজা খোলে: window-কে সংখ্যা বানিয়ে slide করলে key update হয় O(1)-এ।

3. What is the hidden math or logic?¶

লুকানো logic: একটা দৈর্ঘ্য-n string-এ ঠিক n - 10 + 1টা 10-অক্ষরের window আছে — একটা একটা করে এক ঘর ডানে সরে। duplicate ধরা মানে "এই window-টা কি আগের কোনো position-এ হুবহু এসেছিল?" — অর্থাৎ window-কে একটা identity (key) দিয়ে seen-set-এ খোঁজা। rolling hash-এর গণিতটা হলো positional/place-value: string-কে কোনো base-এর সংখ্যা ধরে, window slide করলে বেরিয়ে-যাওয়া অক্ষরের contribution বিয়োগ, বাকিটা multiply, ঢোকা অক্ষর যোগ — সবই modular arithmetic (../../01-math-based-programming-fundamentals/02-modular-arithmetic/)।

4. Which data structure is needed?¶

দুটো hash set: একটা seen (এ পর্যন্ত দেখা সব window-key), আর একটা repeated (যেগুলো অন্তত দুবার এসেছে — যাতে উত্তরে ডুপ্লিকেট না ঢোকে)। set কারণ আমাদের শুধু "আছে কি নেই" আর "অনন্য কি না" দরকার, count নয়।

5. Why this data structure fits¶

প্রতিটা window-এ আমরা জিজ্ঞেস করি "এই key কি seen-এ আছে?" — set গড়ে O(1)। থাকলে repeated-এ যোগ (set হওয়ায় একই window বহুবার এলেও উত্তরে একবারই)। list হলে প্রতিবার membership-check O(n) হতো, পুরোটা O(n^2)। set সেই খোঁজাকে instant করে আর অনন্যতা ফ্রি-তে রাখে।

6. Real-life analogy¶

ভাবো তুমি একটা লম্বা গানের প্রতিটা ১০-সেকেন্ডের টুকরো শুনছ আর ভাবছ "এই সুরটা কি আগে শুনেছি?"। তুমি প্রতিবার পুরো গান আবার শোনো না — মাথায় শোনা টুকরোগুলোর একটা সেট রাখো; নতুন টুকরো এলেই সেই সেটে মিলিয়ে দেখো। যেটা দ্বিতীয়বার বাজল, সেটাকে "পুনরাবৃত্ত" তালিকায় তোলো — কিন্তু একবারই, যতবারই বাজুক।

7. Visual explanation¶

ছোট করে দৈর্ঘ্য-3 window দিয়ে ধারণাটা (আসল problem-এ 10): s = "AAAAA"। window এক ঘর করে সরে, seen-এ মেলে কি না দেখি:

i=0  win="AAA"  AAA in {}?        না   → seen={AAA}
i=1  win="AAA"  AAA in seen?      হ্যাঁ → repeated={AAA}
i=2  win="AAA"  AAA in seen?      হ্যাঁ → repeated={AAA}  (set, তাই একবারই)
উত্তর: ["AAA"]

প্রতিবার শুধু এক ঘর ডানে সরছি; rolling hash থাকলে এই slide-এ key-ও O(1)-এ আপডেট হতো।

8. Example input and output¶

Input : "AAAAACCCCCAAAAACCCCCCAAAAAGGGGG"   Output: ["AAAAACCCCC", "CCCCCAAAAA"]
Input : "AAAAAAAAAAAAA"  (13টা A)            Output: ["AAAAAAAAAA"]
Input : "AAAAAAAAA"      (দৈর্ঘ্য 9)          Output: []   (10-window-ই হয় না)
Input : "ACGTACGTAC"     (দৈর্ঘ্য ঠিক 10)     Output: []   (একটাই window, পুনরাবৃত্তি নেই)

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা 10-window নাও, তারপর তার ডানের প্রতিটা 10-window-র সাথে মিলিয়ে দেখো একই কি না।

প্রতিটা শুরু i-র জন্য:
    win = s[i : i+10]
    প্রতিটা j > i-র জন্য:
        s[j : j+10] == win হলে win-কে উত্তরে রাখো

10. Why brute force is slow¶

দুটো nested loop, প্রতিটায় আবার 10-অক্ষর তুলনা — মোটামুটি O(n^2 · 10)। অপচয়টা seen-set-এর মতোই: প্রতিটা window-র জন্য আমরা সামনের পুরো string আবার scan করছি, যদিও "আগে দেখেছি কি না" প্রশ্নটা একটা set একবারেই বলে দিতে পারে। সামনে খোঁজা বন্ধ করে পেছনের স্মৃতিতে তাকালেই O(n)।

11. Key observation¶

মূল observation: "পরে repeat করবে?" প্রশ্নটা উল্টে "আগে এসেছিল?"-তে আনা যায় — আর সেটা seen-set গড়ে O(1)-এ বলে। প্রতিটা window-কে একটা key ভাবো; key আগে set-এ থাকলেই duplicate। উত্তরের অনন্যতা ধরতে দ্বিতীয় একটা set যথেষ্ট।

12. Optimized intuition¶

string-এর উপর একবার হাঁটো, প্রতিটা শুরু i-তে window = s[i:i+10] নাও। window যদি seen-এ থাকে → repeated-এ যোগ করো; নইলে seen-এ যোগ করো। শেষে repeated-এর সব element ফেরত দাও। এক pass, প্রতিটা window key O(1) (rolling hash হলে slice-ও O(1))। মোট কার্যত O(n)।

13. Thinking tweak¶

মোচড়: একটা window-কে একটা একক "জিনিস" (key) ভাবো, তারপর seen-set-এর "আগে দেখেছি?" সরাসরি লাগাও। এক ধাপ এগিয়ে — সেই key-কে slice না বানিয়ে একটা rolling সংখ্যা বানালে প্রতিটা slide O(1)। এই "window → key → set" চিন্তাই string matching, anagram-window, repeated-substring সব জায়গায় ফিরে আসে।

14. Step-by-step dry run¶

Input s = "AAAAAAAAAAAAA" (13টা A), window দৈর্ঘ্য 10:

শুরু: seen = {}, repeated = {}। window সংখ্যা 13 - 10 + 1 = 4।
i=0: win = "AAAAAAAAAA"; seen-এ নেই → seen = {"AAAAAAAAAA"}।
i=1: একই win; seen-এ আছে → repeated = {"AAAAAAAAAA"}।
i=2, i=3: আবার একই win; ইতিমধ্যে repeated-এ আছে, set হওয়ায় বদল নেই।
উত্তর: ["AAAAAAAAAA"]।

15. Python solution¶

def find_repeated_dna(s):
    seen = set()                       # এ পর্যন্ত দেখা সব 10-window
    repeated = set()                   # যেগুলো অন্তত দুবার এসেছে
    for i in range(len(s) - 9):        # শেষ শুরু-index = len(s) - 10
        window = s[i:i + 10]
        if window in seen:             # আগে দেখেছি? → পুনরাবৃত্ত
            repeated.add(window)
        else:
            seen.add(window)
    return sorted(repeated)            # স্থির ক্রমে ফেরত (test-এর সুবিধায়)

# ---- tests ----
assert find_repeated_dna("AAAAACCCCCAAAAACCCCCCAAAAAGGGGG") == ["AAAAACCCCC", "CCCCCAAAAA"]
assert find_repeated_dna("AAAAAAAAAAAAA") == ["AAAAAAAAAA"]   # 13টা A
assert find_repeated_dna("AAAAAAAAA") == []                  # দৈর্ঘ্য 9, window-ই হয় না
assert find_repeated_dna("ACGTACGTAC") == []                # ঠিক 10, একটাই window
print("সব test pass!")

16. Line-by-line code explanation¶

seen = set() — এ পর্যন্ত দেখা প্রতিটা 10-অক্ষর window জমে।
repeated = set() — যেগুলো দ্বিতীয়বার দেখা গেছে; set হওয়ায় উত্তরে কখনো ডুপ্লিকেট নয়।
for i in range(len(s) - 9) — শুরু-index 0 থেকে len(s) - 10 পর্যন্ত; range(len(s) - 9) ঠিক ততগুলো দেয়।
window = s[i:i + 10] — এখনকার 10-অক্ষর টুকরো; এটাই আমাদের key।
if window in seen — set membership গড়ে O(1); আগে থাকলে এটি পুনরাবৃত্ত।
repeated.add(window) / seen.add(window) — হয় পুনরাবৃত্ত তালিকায়, নয়তো প্রথমবার দেখা হিসেবে নথিভুক্ত।
return sorted(repeated) — set-এর ক্রম অনিশ্চিত, তাই sort করে স্থির উত্তর (assert মেলানো সহজ)।

17. Output walkthrough¶

প্রথম case-এ "AAAAACCCCC" ও "CCCCCAAAAA" দুটোই দ্বিতীয়বার দেখা যায় → sort করে ["AAAAACCCCC", "CCCCCAAAAA"]। 13টা A-তে একই 10-window চারবার আসে, কিন্তু set হওয়ায় উত্তর ["AAAAAAAAAA"]। দৈর্ঘ্য 9-এ loop চলেই না → []। ঠিক 10 দৈর্ঘ্যে একটাই window, পুনরাবৃত্তি নেই → []। শেষে print: সব test pass!।

18. Time complexity¶

O(n) কার্যত — n window, প্রতিটায় slice + set operation। Python slice 10-অক্ষর কপি করে (ধ্রুবক 10), তাই গড়ে O(n)। rolling hash দিয়ে slice-ও O(1) করা যায়, constant ছোট হয়।

19. Space complexity¶

O(n) — worst case-এ প্রায় সব আলাদা window দুই set-এ জমতে পারে।

20. Common mistakes¶

window-সীমা ভুল করা — শেষ বৈধ শুরু-index len(s) - 10; range(len(s) - 9) ঠিক, range(len(s) - 10) শেষ window বাদ দেয়, range(len(s)) সীমা ছাড়ায়।
উত্তরে ডুপ্লিকেট আসা — একই window তিনবার এলে list-এ তিনবার ঢুকে যেতে পারে; repeated কে set রাখলে সমস্যা নেই।
দৈর্ঘ্য < 10 case ভুলে যাওয়া — তখন কোনো window-ই হয় না; loop ফাঁকা চললে স্বাভাবিকভাবেই [] ফেরে, কিন্তু সীমা ভুল হলে index error হতে পারে।

21. Which basic problem this inherits from¶

ভিত্তি: seen-set (Pattern 4, Contains Duplicate #2-এর আত্মীয়) — শুধু element এখন একটা গোটা substring window। এই note rolling hash (Pattern 7)-এর প্রবেশদ্বার: window-কে key ভাবা, আর সেই key-কে slide-এ O(1) আপডেট করার ধারণা। rolling hash-এর গণিত আসে ../../01-math-based-programming-fundamentals/02-modular-arithmetic/ থেকে। সম্পূর্ণ আলোচনা ../patterns.md-র Pattern 4 ও 7-এ।

22. Similar harder problems¶

Longest Duplicate Substring — https://leetcode.com/problems/longest-duplicate-substring/ (rolling hash + binary search; এই idea-র hard রূপ)
Find All Anagrams in a String — https://leetcode.com/problems/find-all-anagrams-in-a-string/ (fixed-window frequency counting)
Distinct Echo Substrings — https://leetcode.com/problems/distinct-echo-substrings/ (rolling hash দিয়ে substring তুলনা)

23. Pattern learned¶

Seen-set of windows (rolling-hash teaser): প্রতিটা fixed-length window-কে একটা key ভাবো, seen-set-এ "আগে দেখেছি?" জিজ্ঞেস করো; অনন্যতা ধরতে দ্বিতীয় set। এক ধাপ উপরে — key-কে rolling hash বানালে প্রতিটা slide O(1)।

24. Final summary¶

ভবিষ্যতের আমাকে: "repeated substring / একই দৈর্ঘ্যের টুকরো বারবার এসেছে কি" শুনলেই window → key → seen-set মনে পড়বে। মূল চাল — "পরে repeat?" কে "আগে এসেছিল?"-তে উল্টে দাও। আর যদি window অনেক বা বড় হয়, slice-এর বদলে rolling hash — সেটাই Pattern 7-এর দিকে পরের ধাপ (#22 Codeforces pick-এ পুরো রূপে)।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।