# Arrays and Strings — Problem-Solving Patterns

Pattern মানে আসলে চিন্তার একটা reusable *আকার*। Trigger word গুলো শেখো, core idea টা ধরো, আর সেই একটা mental tweak শেখো যেটা brute-force O(n^2) loop-কে একটা পরিষ্কার O(n) solution-এ বদলে দেয়।

---

## Pattern 1 — Two Pointers

**Trigger words:** "pair that sums to...", "remove duplicates in place", "sorted array", "palindrome", "container / pair of walls", "move all zeros"।

**Core idea:** দুটো nested loop দিয়ে সব pair try করার (O(n^2)) বদলে দুটো index রাখো আর সেগুলোকে *উদ্দেশ্য* নিয়ে সরাও — সাধারণত দুই প্রান্ত থেকে ভেতরের দিকে, অথবা বাঁ দিক থেকে একটা slow আর একটা fast।

**Thinking tweak:** pointer-এর প্রতিটা move-এ কিছু candidate চিরতরে বাদ পড়তে হবে। তুমি যদি argue করতে পারো "L ডানে সরালে answer কখনো হারাতে পারি না", তাহলে তোমার হাতে একটা correct O(n) algorithm আছে।

**Worked example — sorted `[1, 3, 4, 6, 9]`-এ 10-এ sum হয় এমন pair:**

```text
L=1, R=9 -> sum 10  FOUND.
(if sum had been < target: only moving L right can increase it;
 if sum had been > target: only moving R left can decrease it —
 each step kills one element forever, so at most n steps.)
```

**Inherits from:** সাধারণ array traversal + sorted-order invariant।

**Representative problems:**

- Sorted input-এ two-pointer pair sum — [LeetCode 167](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/)
- Container-এর দেয়ালের সেরা pair — [LeetCode 11](https://leetcode.com/problems/container-with-most-water/) — [Container With Most Water: বাংলা নোট](problems/012-container-most-water.md)
- সব zero-sum triple — [LeetCode 15](https://leetcode.com/problems/3sum/) — [3Sum: বাংলা নোট](problems/016-three-sum.md)

## Pattern 2 — Sliding Window

**Trigger words:** "longest/shortest **substring** বা **subarray**", "at most K distinct", "contains all characters of", "window of size k"।

**Core idea:** এমন একটা window `[L..R]` maintain করো যেটা সবসময় শর্ত মানে (বা মানার চেষ্টা করছে)। বড় করতে `R` expand করো; শর্ত ভাঙলেই শুধু `L` shrink করো। প্রতিটা index একবার ঢোকে একবার বের হয় → O(n)।

**Thinking tweak:** কিছু ভাঙলে কখনো window টা scratch থেকে restart করো না। বাঁ প্রান্ত sliding করে *repair* করো — মাঝের element গুলোর জন্য করা কাজটা এখনো valid।

**Worked example — `"abcabcbb"`-এর repeat-ছাড়া longest substring:**

```text
grow:  a -> ab -> abc        (best = 3)
R hits second 'a': duplicate! slide L past the first 'a'
R=3: bca, L=1, best=3
R=4: cab, L=2, best=3
R=5: abc, L=3, best=3
R=6: cb,  L=5, best=3
R=7: b,   L=7, best=3
```

**শর্তের সীমা:** positive/nonnegative number-এর sum সীমা ছাড়ালে shrink করা কাজে লাগে; negative number থাকলে এই monotonic যুক্তি ভাঙতে পারে। Exact sum count করতে [prefix + hash map](problems/015-subarray-sum-k.md) দেখো। Minimum window-এ invalid হলে expand, valid হলে shrink — longest-valid window-এর নিয়ম সরাসরি কপি করবে না।

**Inherits from:** two pointers (এটা আসলে একই দিকে চলা two pointers-ই) + window-র contents-এর জন্য frequency counting।

**Representative problems:**

- Repeating character ছাড়া longest substring — [LeetCode 3](https://leetcode.com/problems/longest-substring-without-repeating-characters/) — [Longest Substring Without Repeating Characters: বাংলা নোট](problems/010-longest-unique-substring.md)
- t-এর সবকিছু cover করা minimum window — [LeetCode 76](https://leetcode.com/problems/minimum-window-substring/) — [Minimum Window Substring: বাংলা নোট](problems/020-minimum-window-substring.md)
- Fixed size k-এর যেকোনো subarray-র max sum — classic fixed-window warm-up, দেখো [USACO Guide](https://usaco.guide/)-এর sliding-window module

## Pattern 3 — Prefix Sums

**Trigger words:** "sum of range [l, r]", "many queries", "count subarrays with sum K", "equilibrium / pivot index"।

**Core idea:** আগে থেকে হিসাব করে রাখো `prefix[i]` = প্রথম `i`-টা element-এর sum। তাহলে যেকোনো range sum নেমে আসে একটা subtraction-এ: `sum(l..r) = prefix[r+1] - prefix[l]`।

**Thinking tweak:** "subarray sum equals K" হয়ে যায় "আমি কি আগে `current_prefix - K` সমান কোনো prefix দেখেছি?" — দেখা prefix গুলো একটা hash map-এ রাখো, আর এক pass-এই এমন সব subarray count হয়ে যাবে।

**Worked example — `[1, 2, 1]`-এর কয়টা subarray-র sum 3:**

```text
prefixes seen: {0:1}
running=1 -> need 1-3=-2, absent. record 1.
running=3 -> need 3-3=0, seen once! count=1. record 3.
running=4 -> need 4-3=1, seen once! count=2.       answer: 2  ([1,2] and [2,1])
```

**Inherits from:** prefix/difference/contribution chapter — পুরো derivation আর difference-array জমজটার জন্য দেখো [../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)।

**Representative problems:**

- Subarray sum equals K — [LeetCode 560](https://leetcode.com/problems/subarray-sum-equals-k/) — [Subarray Sum Equals K: বাংলা নোট](problems/015-subarray-sum-k.md)
- Product of array except self (prefix products) — [LeetCode 238](https://leetcode.com/problems/product-of-array-except-self/) — [Product of Array Except Self: বাংলা নোট](problems/014-product-except-self.md)
- Static Range Sum Queries — [CSES Problem Set](https://cses.fi/problemset/task/1646/), task "Static Range Sum Queries" — [Static Range Sum Queries: বাংলা নোট](problems/009-static-range-sum.md)

## Pattern 4 — In-Place Reversal and Rotation

**Trigger words:** "rotate by k", "in place", "O(1) extra space", "reverse words/sections"।

**Core idea:** Two pointers দিয়ে reversal-এর খরচ O(n) time আর O(1) space। k দিয়ে rotation মানে **তিনটা reversal**: পুরো array reverse করো, তারপর প্রথম k-টা reverse করো, তারপর বাকিটা reverse করো।

**Thinking tweak:** rotation শুনলে মনে হয় একটা temporary array লাগবেই — কিন্তু দুইবার reverse করলে প্রতিটা block আবার forward order-এ ফিরে আসে, অথচ block দুটো নিজেদের মধ্যে জায়গা বদলে ফেলেছে।

**Worked example — `[1, 2, 3, 4, 5]` কে ডানে k = 2 rotate করো:**

```text
reverse all:        [5, 4, 3, 2, 1]
reverse first 2:    [4, 5, 3, 2, 1]
reverse last 3:     [4, 5, 1, 2, 3]   done — the last two items moved to the front
```

**Inherits from:** Pattern 1-এর two-pointer swap।

**Representative problems:**

- Rotate array — [LeetCode 189](https://leetcode.com/problems/rotate-array/) — [Rotate Array: বাংলা নোট](problems/013-rotate-array.md)
- In place string reverse — [LeetCode 344](https://leetcode.com/problems/reverse-string/) — [Reverse String: বাংলা নোট](problems/001-reverse-string.md)
- String-এর word গুলো reverse — [LeetCode 151](https://leetcode.com/problems/reverse-words-in-a-string/)

## Pattern 5 — Frequency Counting

**Trigger words:** "anagram", "first unique", "majority", "appears exactly/at least k times", "permutation of each other"।

**Core idea:** এক O(n) pass-এ একটা dict-এ (বা `collections.Counter`-এ) occurrence count করো, তারপর বারবার re-scan না করে count গুলো থেকেই প্রশ্নের উত্তর দাও।

**Thinking tweak:** দুটো string anagram **iff** তাদের count map সমান — arrangement না, summary compare করো। Lowercase letter-এর জন্য 26-slot-এর একটা array আরো সস্তা counter।

**Worked example — `"listen"` কি `"silent"`-এর anagram?**

```text
count("listen") = {l:1, i:1, s:1, t:1, e:1, n:1}
count("silent") = {s:1, i:1, l:1, e:1, n:1, t:1}
maps equal -> YES, in O(n), without trying any of the n! orderings
```

**Inherits from:** সাধারণ traversal + hash-map idea (constant-time lookup)।

**Representative problems:**

- Valid anagram — [LeetCode 242](https://leetcode.com/problems/valid-anagram/) — [Valid Anagram: বাংলা নোট](problems/003-valid-anagram.md)
- Canonical key দিয়ে group anagrams — [LeetCode 49](https://leetcode.com/problems/group-anagrams/) — [Group Anagrams: বাংলা নোট](problems/017-group-anagrams.md)
- Top k frequent elements — [LeetCode 347](https://leetcode.com/problems/top-k-frequent-elements/)

## Pattern 6 — String Building (O(n^2) trap এড়াও)

**Trigger words:** "construct the result string", "transform/encode/decode", "repeat n times", যেকোনো loop যেটা একটা string বাড়াচ্ছে।

**Core idea:** string immutable, তাই `s += piece` প্রতিবার পুরো `s` copy করে — ওরকম একটা loop মানে O(n^2)। টুকরোগুলো একটা list-এ জমাও আর শেষে একবার `''.join` করো: O(n)।

**Thinking tweak:** answer string-টাকে *একদম শেষ মুহূর্ত পর্যন্ত frozen* ধরে নাও। Final `join`-এর আগ পর্যন্ত সবকিছু স্রেফ fragment-এর একটা list।

**Worked example — `"aaabb"`-এর run-length encode:**

```text
parts = []
run 'a' x3 -> parts = ["a", "3"]
run 'b' x2 -> parts = ["a", "3", "b", "2"]
"".join(parts) -> "a3b2"        every character written exactly once
```

**Inherits from:** dynamic array-র append-is-cheap property (চাইলে একে Pattern 0 বলতে পারো)।

**Representative problems:**

- In place string compression — [LeetCode 443](https://leetcode.com/problems/string-compression/)
- Zigzag conversion (row বানাও, join করো) — [LeetCode 6](https://leetcode.com/problems/zigzag-conversion/)
- `3[a2[c]]`-এর মতো string decode — [LeetCode 394](https://leetcode.com/problems/decode-string/) (এটা [../04-stack-and-queue/](../04-stack-and-queue/README.md)-এর stack pattern-এরও একটা preview) — [Decode String: বাংলা নোট](problems/019-decode-string.md)

## Pattern 7 — Kadane's Algorithm (maximum subarray)

**Trigger words:** "maximum sum of a contiguous subarray", "best segment", "maximum product subarray" (variant)।

**Core idea:** বাঁ থেকে ডানে হাঁটো আর রাখো `best_ending_here` = *current index-এ শেষ হওয়া* সেরা subarray। প্রতিটা element-এ choose করো: আগের run টা extend করবে, নাকি এখান থেকে fresh শুরু করবে।

**Thinking tweak:** negative running total মানে মরা ওজন — সামনে যা-ই আসুক সেটাকে শুধু টেনে নামাবে, তাই ওটা ফেলে দাও আর restart করো। প্রতি element-এ একটা local decision-ই global answer দিয়ে দেয়।

**Worked example — `[-2, 1, -3, 4, -1, 2, 1]`:**

```text
x=-2: initialize end=-2, best=-2
x= 1: prev end -2 < 0 -> restart: end=1     best=1
x=-3: end=1-3=-2                   best=1
x= 4: prev end -2 < 0 -> restart: end=4     best=4
x=-1: end=4-1=3                    best=4
x= 2: end=3+2=5                    best=5
x= 1: end=5+1=6                    best=6   -> answer 6 (subarray [4,-1,2,1])
```

**Inherits from:** prefix-sum চিন্তা — `prefix[j]` প্রথম j-টি element-এর sum হলে `best ending at i = prefix[i+1] - min(prefix[0..i])`, আর Kadane's সেই minimum-টাই implicitly track করে। অনেকের জীবনের প্রথম dynamic-programming recurrence-ও এটাই।

**Representative problems:**

- Maximum subarray — [LeetCode 53](https://leetcode.com/problems/maximum-subarray/) — [Maximum Subarray: বাংলা নোট](problems/011-maximum-subarray.md)
- Best time to buy and sell stock (running-min variant) — [LeetCode 121](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/) — [Best Time to Buy and Sell Stock: বাংলা নোট](problems/007-buy-sell-stock.md)
- Maximum product subarray (min ও max track করো) — [LeetCode 152](https://leetcode.com/problems/maximum-product-subarray/)

---

## Pattern cheat sheet

| Pattern | Killer trigger | Brute force-কে হারায় কারণ |
| --- | --- | --- |
| Two pointers | "pair/triple in sorted data", "in place" | প্রতিটা move candidate চিরতরে বাদ দেয় |
| Sliding window | "longest/shortest sub*" | restart না, repair করো |
| Prefix sums | "range sum", "subarrays summing to K" | একবার precompute, উত্তর O(1)-এ |
| Reversal/rotation | "rotate by k, O(1) space" | তিনটা reversal temp array-র জায়গা নেয় |
| Frequency counting | "anagram/unique/majority" | arrangement না, summary compare |
| String building | string বাড়ানো যেকোনো loop | join প্রতিটা char একবারই copy করে, n বার না |
| Kadane's | "max contiguous sum" | negative prefix greedily ফেলে দাও |

এবার [implementation.py](./implementation.py)-র from-scratch build গুলো পড়ো, তারপর [problems/README.md](./problems/README.md)-তে tracker শুরু করো।