# Arrays ও Strings — দুই ডিভাইসের study report

একই পড়ার অ্যাপ ফোন ও ল্যাপটপে চালিয়েছ। দুই ডিভাইসের session আলাদাভাবে সময় অনুযায়ী সাজানো। একটি report-এ সেগুলো মিলিয়ে দেখতে হবে: নির্দিষ্ট অংশে কত score, একই বিষয় পুনরাবৃত্তি ছাড়া দীর্ঘতম অংশ কোনটি, এবং মোট score সবচেয়ে বেশি এমন টানা অংশ কোনটি। এই একটি report-এ merge, prefix sum, sliding window ও Kadane একসঙ্গে কাজে লাগবে।

**কোর্স-সংযোগ:** Microsoft কোর্সের Module 1-এর arrays/complexity এবং Module 2-এর sorted data নিয়ে কাজ করার অনুশীলন। এটি এই সাইটের নিজস্ব সমস্যা; কোর্সের official assignment নয়।

## ১. শুরু করার আগে যা পড়বে

| ক্রম | পড়া ও অনুশীলন | নিজেকে যে প্রশ্ন করবে |
| --- | --- | --- |
| 1 | [Array-এর ধারণা](../02-arrays-and-strings/concept.md), [চিত্র](../02-arrays-and-strings/visual-explanation.md) | index ও value আলাদা কেন? |
| 2 | [Merge Sorted Array](../02-arrays-and-strings/problems/005-merge-sorted-array.md) | দুই input-এর পরের ছোট মান কোথায়? |
| 3 | [Static Range Sum](../02-arrays-and-strings/problems/009-static-range-sum.md) | `prefix[0] = 0` রাখলে সুবিধা কী? |
| 4 | [Longest Unique Substring](../02-arrays-and-strings/problems/010-longest-unique-substring.md) | duplicate পেলে বাঁ পাশ কত দূর যাবে? |
| 5 | [Maximum Subarray](../02-arrays-and-strings/problems/011-maximum-subarray.md) | আগের negative যোগফল রেখে লাভ হয় কি? |

## ২. সমস্যার চুক্তি

`session_report(left, right, queries)` বানাও। প্রতিটি session হলো `(time, tag, score)`। `time` ও `score` integer; `tag` একটি খালি নয় এমন string। score negative হতে পারে, যেমন ভুল উত্তর বা penalty। প্রতিটি input সময়ের ছোট থেকে বড় ক্রমে থাকবে। সমান সময় হলে `left`-এর session আগে নেবে; একই batch-এর ক্রমও রাখবে। input বদলানো যাবে না।

- দুই batch মিলিয়ে `0 ≤ n ≤ 100000`; `0 ≤ q ≤ 100000` query।
- প্রতিটি query `(start, end)` **মিলিত array-র index**; `[start, end)` মানে start থাকবে, end থাকবে না। `0 ≤ start ≤ end ≤ n`। খালি range-এর যোগফল 0।
- `unique_span`: tag পুনরাবৃত্তি নেই এমন দীর্ঘতম span। সমান দৈর্ঘ্যে সবচেয়ে বাঁয়েরটি। খালি input-এ `(0, 0)`। tag-এর case বদলাবে না: `A` ও `a` আলাদা।
- `best_score`: সর্বোচ্চ score-এর **খালি নয়** এমন contiguous span ও score। সমান score হলে ছোট start, তারপর ছোট end। খালি input-এ `None`।
- ভুল sorted order, খালি tag বা ভুল query পেলে `ValueError`।

### হাতে করা উদাহরণ

```python
left = [(1, "A", 3), (3, "B", -2)]
right = [(2, "C", 4), (4, "A", 5)]
queries = [(0, 3), (2, 4)]
```

```dsa
kind: array
title: "মিলিত session-এর score; নিচের index দিয়েই query"
steps:
  - label: "সময় 1, 2, 3, 4 — tag A, C, B, A"
    values: [3, 4, -2, 5]
    active: [0, 1, 2]
    note: "প্রথম তিন tag আলাদা। শেষ A এলে বাঁ পাশ 0 থেকে 1 হয়; আগের span-ই tie-তে জেতে।"
  - label: "প্রথম ঘর 0 রেখে prefix তৈরি"
    values: [0, 3, 7, 5, 10]
    active: [0, 3]
    note: "[0,3)-এর score = prefix[3] − prefix[0] = 5।"
```

প্রত্যাশিত output:

```python
{
    "sessions": [(1, "A", 3), (2, "C", 4), (3, "B", -2), (4, "A", 5)],
    "range_scores": [5, 3],
    "unique_span": (0, 3),
    "best_score": {"score": 10, "span": (0, 4)},
}
```

দ্বিতীয় query-তে `-2 + 5 = 3`। সবচেয়ে লাভজনক span পুরো array: `3 + 4 - 2 + 5 = 10`।

## ৩. চারটি guided milestone

### ধাপ A — সময় অনুযায়ী এক করা

`merge_sessions(left, right)` লিখো। `i` ও `j` দিয়ে দুই batch-এর পরের unread session বোঝাও। ছোট timestamp-টি output-এ রাখো; শুধু সেই pointer বাড়াও। এক batch শেষ হলে অন্যটির বাকি অংশ নাও।

**Invariant:** output-এ এখন পর্যন্ত নেওয়া সব session সঠিক ক্রমে আছে; `i + j` হলো নেওয়া session-এর সংখ্যা। Hint: timestamp সমান হলে `<=` ব্যবহার করলেই left আগে থাকবে।

**Checkpoint:** `test_stable_merge`, `test_no_input_mutation`, `test_unsorted_and_invalid_session` পাস করো। নিজের কাগজে দুটি batch-এ একই timestamp দিয়ে trace করো।

### ধাপ B — query-র উত্তর এক বিয়োগে

`prefix_scores(scores)`-এ length `n + 1` prefix বানাও। তারপর `range_scores(prefix, queries)` লিখো। এখানে `prefix[i]`-তে index `i`-এর মান নেই; আছে তার **আগের** সব মানের যোগফল।

**Invariant:** `prefix[i + 1] = prefix[i] + scores[i]`। Hint: `[start,end)`-এর উত্তর `prefix[end] - prefix[start]`; `end + 1` ব্যবহার করবে না।

**Checkpoint:** খালি query `(2,2)`-এর উত্তর 0, এবং sample-এর দুই উত্তর `[5,3]`। invalid query যেন array থেকে ভুল মান পড়তে না পারে।

### ধাপ C — একই tag ছাড়া দীর্ঘতম অংশ

`longest_unique_span(tags)`-এ `last[tag]` রাখো। প্রতিটি ডান প্রান্তে duplicate-এর আগের অবস্থান দেখে `start = max(start, last[tag] + 1)` করো। তারপর last update করো।

**Invariant:** `[start,end]`-এ কোনো tag দুইবার নেই এবং start কখনো পিছোয় না। Hint: `abba`-তে শেষ `a` দেখে start পিছিয়ে দিলে ভুল হবে। শুধু কঠোরভাবে বড় দৈর্ঘ্য পেলেই best বদলালে tie-র নিয়ম মেনে চলবে।

**Checkpoint:** `abba → (0,2)`; সব tag আলাদা হলে পুরো array।

### ধাপ D — সবচেয়ে ভালো contiguous score ও সম্পূর্ণ report

`best_score_span(scores)` লিখো। প্রতিটি index-এ দুটি পথ: বর্তমান score দিয়ে নতুন span শুরু, অথবা আগের span বাড়ানো। আগের চলতি sum negative হলেই নতুন শুরু করো। শূন্য হলে আগের start রাখলে earliest-start tie ঠিক থাকে।

**Invariant:** চলতি sum হলো বর্তমান index-এ শেষ হওয়া সেরা span-এর sum। পুরো input-এর best আলাদা করে রাখো। সব score negative হলেও একটি session বেছে নিতে হবে।

**Checkpoint:** `[-3,-1,-1] → score -1, span (1,2)`; `[0,1,-1,1] → score 1, span (0,2)`। এবার চার helper-কে `session_report`-এ যুক্ত করো।

## ৪. Unit test, solution ও নিজের যাচাই

[Python reference implementation](../practice/arrays_lab.py) · [Unit tests](../practice/test_arrays_lab.py)

প্রথমে উপরের function contract ধরে নিজে implement করো। reference-এ দুই pointer, একটি prefix array, একটি last-position dictionary ও একটি চলতি sum কীভাবে একই report-এ পৌঁছায় তা পরে মিলিয়ে দেখো। ফাইল দুটি project-এর `practice/` folder-এ রেখে root থেকে চালাও:

```bash
python -m unittest discover -s practice -p 'test_arrays_lab.py' -v
```

৯টি test-এ sample, stable merge, input না-বদলানো, empty input, invalid query এবং negative/tie আছে। আরও ১৫০টি ছোট random case-এ window ও best score-কে সব সম্ভব span পরীক্ষা করা ধীর সমাধানের সঙ্গে মেলানো হয়। শুধু sample পাস হওয়া যথেষ্ট নয়।

## ৫. কী যুক্ত হলো, কী আলাদা পড়তে হবে

| Technique | এই সমস্যায় ব্যবহার |
| --- | --- |
| Two pointers | sorted session merge |
| Prefix sum | index-range score query |
| String equality + sliding window | পুনরাবৃত্তি ছাড়া tag-এর span |
| Kadane + tie handling | সর্বোচ্চ score-এর contiguous span |
| আলাদা অনুশীলন | rotation, anagram grouping, minimum-cover window, rain water ও KMP এই report-এর অংশ নয় |

সব helper মিলিয়ে সময় `O(n + q)`; report, prefix ও tag map-সহ অতিরিক্ত memory `O(n + q)`। range query করার পরে score বদলালে পুরনো prefix অচল হবে—এই সংস্করণে update নেই। পরের চ্যালেঞ্জ: score update দরকার হলে [Fenwick/Segment Tree](../11-segment-tree-and-fenwick-tree/README.md) ব্যবহার করে report-এর range অংশ বদলাও।