# Arrays and Strings — বাক্সে বাক্সে বোঝা

Array-এর প্রতিটি বাক্স একটি position; index দিয়ে সেই position খুঁজে পাই। রঙ করা বাক্সে বর্তমান কাজটি হচ্ছে। আগে পরের অবস্থা অনুমান করো, তারপর ধাপটি দেখো।

## 1. Append: জায়গা থাকলে শুধু শেষের বাক্সটি লেখো

**Size** হলো ব্যবহৃত ঘরের সংখ্যা, **capacity** হলো মোট বরাদ্দ ঘর। এখানে capacity 4, কিন্তু শুরুতে 3টি ঘর ব্যবহৃত।

```dsa
kind: array
title: "append(9): পুরনো কোনো মান সরাতে হয় না"
steps:
  - label: "আগে · size 3, capacity 4"
    values: [5, 2, 7, "—"]
    muted: [3]
    pointers: {write: 3}
    note: "শেষের খালি ঘরেই নতুন মানটি যাবে।"
  - label: "পরে · size 4, capacity 4"
    values: [5, 2, 7, 9]
    active: [3]
    note: "একটি write; এই append-এর খরচ O(1)।"
```

Array ভরা থাকলে বড় block দরকার। শেখার সুবিধার জন্য এখানে capacity দ্বিগুণ করেছি; Python `list` ঠিক এই হারে বাড়ে না।

```dsa
kind: array
title: "append(4): resize হলে পুরনো মানও কপি করতে হয়"
steps:
  - label: "১ · পুরনো block ভরা"
    values: [5, 2, 7, 9]
    note: "size = capacity = 4।"
  - label: "২ · নতুন 8 ঘরের block"
    values: ["—", "—", "—", "—", "—", "—", "—", "—"]
    muted: [0, 1, 2, 3, 4, 5, 6, 7]
    note: "বরাদ্দ হয়েছে, এখনো কোনো মান কপি হয়নি।"
  - label: "৩ · পুরনো চারটি মান কপি"
    values: [5, 2, 7, 9, "—", "—", "—", "—"]
    active: [0, 1, 2, 3]
    muted: [4, 5, 6, 7]
    note: "এই copy-এর খরচ O(n)।"
  - label: "৪ · নতুন মান বসাও"
    values: [5, 2, 7, 9, 4, "—", "—", "—"]
    active: [4]
    muted: [5, 6, 7]
    note: "size 5, capacity 8। পরের তিনটি append-এ resize লাগবে না।"
```

একটি resize ধীর হলেও বহু append-এর মধ্যে তার খরচ ভাগ করলে প্রতি append **amortized O(1)** হয়।

## 2. Insert ও delete: মাঝের ঘরের জন্য সরানো লাগে

Index 1-এ `8` বসাতে আগে ডান প্রান্ত থেকে সরাও। বাঁ দিক থেকে সরালে এখনও না-সরানো মান মুছে যেতে পারে। এখানে খালি ঘরটি চলাচল দেখানোর জন্য; বাস্তবে copy-এর মাঝে একই মান দুই ঘরে সাময়িকভাবে থাকতে পারে।

```dsa
kind: array
title: "insert(1, 8): খালি জায়গা ডান থেকে বাঁয়ে আসে"
steps:
  - label: "শুরু"
    values: [5, 2, 7, 9, "—"]
    muted: [4]
    pointers: {target: 1}
  - label: "9: index 3 থেকে 4"
    values: [5, 2, 7, "—", 9]
    active: [4]
    muted: [3]
  - label: "7: index 2 থেকে 3"
    values: [5, 2, "—", 7, 9]
    active: [3]
    muted: [2]
  - label: "2: index 1 থেকে 2"
    values: [5, "—", 2, 7, 9]
    active: [2]
    muted: [1]
  - label: "8 বসাও"
    values: [5, 8, 2, 7, 9]
    active: [1]
    note: "তিনটি মান সরিয়ে একটি write। মাঝখানে insert সাধারণভাবে O(n)।"
```

Delete-এ বিপরীত কাজ: পরের মানগুলো এক ঘর বাঁয়ে আসে, তারপর size এক কমে।

```dsa
kind: array
title: "delete index 1: পরের মানগুলো ফাঁক পূরণ করে"
steps:
  - label: "8 বাদ দিতে হবে"
    values: [5, 8, 2, 7, 9]
    active: [1]
  - label: "2: index 2 থেকে 1"
    values: [5, 2, "—", 7, 9]
    active: [1]
    muted: [2]
  - label: "7: index 3 থেকে 2"
    values: [5, 2, 7, "—", 9]
    active: [2]
    muted: [3]
  - label: "9: index 4 থেকে 3"
    values: [5, 2, 7, 9, "—"]
    active: [3]
    muted: [4]
    note: "ব্যবহৃত অংশ এখন প্রথম চারটি ঘর; capacity কমতেই হবে এমন নয়।"
```

## 3. Two pointers: দুই প্রান্ত বদলে ভেতরে যাও

`L` ও `R` যে দুটি ঘর দেখায়, সেগুলোর মান swap করি। তারা মিললে বা পরস্পরকে পার হলে থামি।

```dsa
kind: array
title: "[A, B, C, D, E] উল্টানো"
steps:
  - label: "১ · দুই প্রান্ত ধরো"
    values: [A, B, C, D, E]
    active: [0, 4]
    pointers: {L: 0, R: 4}
  - label: "২ · A ও E swap"
    values: [E, B, C, D, A]
    active: [0, 4]
    pointers: {L: 0, R: 4}
  - label: "৩ · ভেতরে এসে B ও D swap"
    values: [E, D, C, B, A]
    active: [1, 3]
    pointers: {L: 1, R: 3}
  - label: "৪ · মাঝখানে দেখা; শেষ"
    values: [E, D, C, B, A]
    pointers: {L: 2, R: 2}
    note: "দুইবার swap হয়েছে। মোট O(n) সময়, O(1) অতিরিক্ত জায়গা।"
```

## 4. Sliding window: repeat হলে বাঁ দিক ছাড়ো

String `abcabcbb`-এ একই অক্ষর ছাড়া দীর্ঘতম contiguous অংশ চাই। `L` থেকে `R` পর্যন্ত ঘরগুলোই বর্তমান window।

```dsa
kind: array
title: "নতুন b ঢুকলে পুরনো b বাদ না যাওয়া পর্যন্ত shrink"
steps:
  - label: "R = 5 · বৈধ window abc"
    values: [a, b, c, a, b, c, b, b]
    active: [3, 4, 5]
    pointers: {L: 3, R: 5}
    note: "window-তে প্রতিটি অক্ষর একবার আছে।"
  - label: "R = 6 · a ও পুরনো b বাদ দেওয়ার পরে"
    values: [a, b, c, a, b, c, b, b]
    active: [5, 6]
    pointers: {L: 5, R: 6}
    note: "নতুন window cb। শুধু একবার L বাড়ালে repeat দূর হতো না।"
```

সব ধাপ নিচে আছে; প্রতিটি row-তে shrink শেষ হওয়ার পরের অবস্থা দেখানো হয়েছে।

| R | নতুন অক্ষর | বাঁ দিক থেকে বাদ | L | window | best length |
| --- | --- | --- | --- | --- | --- |
| 0 | a | কিছু নয় | 0 | `a` | 1 |
| 1 | b | কিছু নয় | 0 | `ab` | 2 |
| 2 | c | কিছু নয় | 0 | `abc` | 3 |
| 3 | a | index 0-এর a | 1 | `bca` | 3 |
| 4 | b | index 1-এর b | 2 | `cab` | 3 |
| 5 | c | index 2-এর c | 3 | `abc` | 3 |
| 6 | b | index 3-এর a, index 4-এর b | 5 | `cb` | 3 |
| 7 | b | index 5-এর c, index 6-এর b | 7 | `b` | 3 |

শর্ত পূরণ হওয়া পর্যন্ত `while` দিয়ে shrink করতে হয়। প্রতিটি index একবার ঢোকে ও একবার বের হয়, তাই মোট সময় **O(n)**।

## 5. Prefix sum: দুটি সীমার পার্থক্যই range sum

`prefix[i]` হলো প্রথম `i`টি মানের যোগফল। শুরুতে অতিরিক্ত `0` রাখলে index 0 থেকে শুরু হওয়া query-ও একই সূত্রে মেলে।

```dsa
kind: array
title: "a[1] থেকে a[3]: 1 + 4 + 1 = 6"
steps:
  - label: "মূল array · চাওয়া তিনটি ঘর"
    values: [3, 1, 4, 1, 5]
    active: [1, 2, 3]
    pointers: {L: 1, R: 3}
  - label: "prefix · ডান সীমার পরে একটি ঘর"
    values: [0, 3, 4, 8, 9, 14]
    active: [1, 4]
    pointers: {L: 1, "R+1": 4}
    note: "prefix[4] − prefix[1] = 9 − 3 = 6।"
```

Prefix বানাতে **O(n)** সময়। এরপর প্রতিটি query-তে `prefix[R + 1] - prefix[L]`, অর্থাৎ **O(1)** কাজ।

## 6. String জোড়া লাগানো: একই অক্ষর বারবার কপি হচ্ছে কি?

সাধারণ immutable-string মডেলে পুরনো string-এর শেষে অক্ষর যোগ করতে নতুন string বানাতে হয়। `abcd` বানানোর পূর্ণ হিসাব:

| নতুন অক্ষর | পুরনো string | নতুন string | পুরনো অক্ষর আবার কপি |
| --- | --- | --- | --- |
| a | খালি | `a` | 0 |
| b | `a` | `ab` | 1 |
| c | `ab` | `abc` | 2 |
| d | `abc` | `abcd` | 3 |

পুরনো অক্ষর কপি `0 + 1 + 2 + 3` বার; নতুন চারটি অক্ষরও লিখতে হয়। সাধারণভাবে মোট খরচ **O(n²)** হতে পারে। কিছু Python implementation বিশেষ ক্ষেত্রে `+=` optimize করে; portable সমাধানে তার উপর নির্ভর করি না।

```mermaid
flowchart LR
  A["a"] --> J["একবার join"]
  B["b"] --> J
  C["c"] --> J
  D["d"] --> J
  J --> O["abcd"]
```

টুকরোগুলো list-এ জমিয়ে শেষে `''.join(parts)` করলে মোট অক্ষরের সংখ্যার অনুপাতে কাজ হয়।

**নিজে চেষ্টা করো:** `[1, 2, 3, 4]` reverse করো; তারপর `[2, 4, 6, 8]`-এর index 1–2-এর যোগফল prefix দিয়ে বের করো। পরের পাঠ: [operations](./operations.md) ও [patterns](./patterns.md)।