Problem link ও উৎস
- **Original source:** Classic grouping-then-sorting exercise
- **Platform:** LeetCode —
- **Topic:** disjoint set union
- **Difficulty:** Medium
- **Pattern:** group then sort inside groups
- **Basic idea inherited from:** `10`-এর grouping pattern + `02-arrays-and-strings`-এর sorting; index union করে group বানাও, প্রতি group-এর ভেতরে char sort করো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা string `s` আর কতগুলো index-pair `pairs` দেওয়া; প্রতিটা pair `[a, b]` মানে `s[a]` আর `s[b]` তুমি যতবার খুশি swap করতে পারো। এই swap-গুলো দিয়ে বানানো যায় এমন **lexicographically smallest** string-টা বের করো।
```text
s = "dcab", pairs = (0-3) (1-2)
index {0,3} নিজেদের মধ্যে swap করা যায়, {1,2}-ও
{0,3}: 'd','b' -> sort -> 'b','d'; {1,2}: 'c','a' -> sort -> 'a','c'
ফল -> "bacd"
```
### Input ও output {#8-example-input-and-output}
```text
Input : s="dcab", pairs=[[0,3],[1,2]]
Output: "bacd"
Input : s="dcab", pairs=[[0,3],[1,2],[0,2]]
Output: "abcd" (সব index এক group)
Input : s="cba", pairs=[[0,1],[1,2]]
Output: "abc"
Edge case (no pairs): s="abc", pairs=[] -> "abc" (কিছুই swap করা যায় না)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো কয়েকটা আলাদা **box**, প্রতিটা box-এ কিছু চিঠি (tiles) আছে — যেগুলো তুমি ওই box-এর ভেতরে যেমন খুশি সাজাতে পারো, কিন্তু এক box থেকে অন্য box-এ সরাতে পারো না। swap-pair গুলো বলে দেয় কোন position-গুলো একই box-এ। সবচেয়ে "ছোট" শব্দ পেতে হলে প্রতিটা box-এর tiles বর্ণানুক্রমে সাজিয়ে box-এর position-গুলোয় বাঁ থেকে ডানে বসাও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
দুটো ভিত একসাথে: এই tracker-এর **grouping pattern (Pattern D)** — যেসব index একে অপরের সাথে (সরাসরি বা ঘুরিয়ে) swap করা যায়, তারা এক group; আর [../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md)-এর **sorting** — প্রতিটা group-এর ভেতরে যেহেতু char-গুলো যেকোনো বিন্যাসে সাজানো যায়, তাই sort করলেই ওই position-গুলোয় smallest বিন্যাস বসে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic দুই ধাপে:
- **swap transitivity:** যদি (a,b) আর (b,c) swap করা যায়, তাহলে a, b, c-র char-গুলো নিজেদের মধ্যে **যেকোনো** order-এ সাজানো যায় — কারণ বারবার swap দিয়ে যেকোনো permutation পাওয়া সম্ভব। তাই connected index-রা একটা equivalence class।
- **lexicographic optimum:** একটা group-এর char-গুলো যদি যেকোনো order-এ বসানো যায়, তাহলে smallest পেতে হলে **ছোট char-গুলো ছোট index-এ** বসাও — অর্থাৎ index গুলো sorted, char গুলোও sorted, তারপর জোড়া মেলাও।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **DSU** (`parent` + `size` array) string-এর length-সমান, প্লাস প্রতি root-এ তার group-এর index জড়ো করার জন্য একটা dictionary/map। DSU দিয়ে group বানাও, map দিয়ে group-প্রতি char sort করে বসাও।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রশ্নের কেন্দ্র — "কোন index-গুলো এক সাথে নাড়াচাড়া করা যায়?" — ঠিক DSU-র grouping প্রশ্ন। swap relation reflexive/symmetric/transitive, তাই index-রা equivalence class-এ ভাগ হয়। DSU সেই class-গুলো near-constant time-এ গড়ে; তারপর প্রতি class-এ sorting বাকি কাজ সারে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: pairs দিয়ে যে যে string-এ পৌঁছানো যায় তার সবগুলো generate করো (বারবার swap চালিয়ে, BFS-এর মতো reachable states ছড়িয়ে), তারপর সবচেয়ে ছোটটা নাও।
```text
1) শুরু string থেকে প্রতিটা swap প্রয়োগ করে নতুন state বানাও
2) সব reachable state একটা set-এ জড়ো করো (BFS)
3) সব state-এর মধ্যে lexicographically smallest-টা ফেরাও
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
Reachable states-এর সংখ্যা group-size-এর factorial পর্যন্ত যেতে পারে — n বড় হলে বিস্ফোরক, সম্পূর্ণ অবাস্তব। DSU পথটা ছোট করে: আসল permutation generate করার দরকারই নেই — শুধু group বের করো (O(P·α)) আর প্রতি group-এ একটা sort (মোট O(n log n))। তাই exponential থেকে near-linear-এ নামে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **একই group-এর char-গুলো যেকোনো order-এ সাজানো যায়।** তাই আসল swap-sequence খোঁজার দরকার নেই — শুধু কোন index-রা এক group, সেটা জানো; তারপর প্রতি group-এ char sort করে sorted index-এ বসাও — সেটাই lexicographic minimum, কারণ ছোট char ছোট index-এ যায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
length-সমান DSU নাও; প্রতিটা pair union করো। তারপর `find(i)` দিয়ে index-গুলোকে group-এ bucket করো (dictionary)। প্রতি group-এর index গুলো sort করো, ওই position-এর char গুলোও sort করো, তারপর জোড়ায় জোড়ায় বসাও (ছোট index ← ছোট char)। সব মিলিয়ে O(n log n + P·α)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কোন swap-গুলো কোন order-এ চালালে smallest পাব?" — এই swap-sequence খোঁজার চিন্তা ছাড়ো। বদলে ভাবো "কোন position-গুলো একই box-এ, সেটা বের করি; তারপর প্রতি box-এ char-গুলো sort করে বসিয়ে দিই।" Process (swap) থেকে structure (group)-এ চিন্তা সরানোই চাবি।
### ছবিতে বোঝা {#7-visual-explanation}
index union করে group; প্রতি group-এর char sort করে, group-এর sorted index-এ বসাও।
```text
s = "dcab", pairs: (0-3) (1-2)
index: 0 1 2 3
char: 'd' 'c' 'a' 'b'
union(0,3): group {0,3}
union(1,2): group {1,2}
group {0,3}: chars at [0,3] = ['d','b'] -> sorted ['b','d']
sorted index [0,3] <- ['b','d'] => s[0]='b', s[3]='d'
group {1,2}: chars at [1,2] = ['c','a'] -> sorted ['a','c']
sorted index [1,2] <- ['a','c'] => s[1]='a', s[2]='c'
ফল: index 0 1 2 3
char 'b''a''c''d' -> "bacd"
------ একটা group হলে: pairs (0-3)(1-2)(0-2) ------
union গুলো 0,1,2,3 সব এক group -> chars ['d','c','a','b'] sorted ['a','b','c','d']
sorted index [0,1,2,3] <- ['a','b','c','d'] -> "abcd"
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `s="dcab", pairs=[[0,3],[1,2]]`:
1. `union(0,3)` → group {0,3}; `union(1,2)` → group {1,2}
2. bucket: `find(0)`=`find(3)` → {0,3} এক bucket; `find(1)`=`find(2)` → {1,2} আরেক bucket
3. bucket {0,3}: char ['d','b'] → sorted ['b','d']; sorted index [0,3] → s[0]='b', s[3]='d'
4. bucket {1,2}: char ['c','a'] → sorted ['a','c']; sorted index [1,2] → s[1]='a', s[2]='c'
5. ফল: `"bacd"`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import defaultdict
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # প্রথমে সবাই নিজের নিজের root
self.size = [1] * n # প্রতিটা group-এ একজন
def find(self, x): # representative + path compression
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, x, y): # union by size; merge হলে True
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False
if self.size[rx] < self.size[ry]:
rx, ry = ry, rx # rx এখন বড় root
self.parent[ry] = rx # ছোটটা বড়টার নিচে ঝোলে
self.size[rx] += self.size[ry]
return True
def smallest_string_with_swaps(s, pairs):
n = len(s)
dsu = DSU(n)
for a, b in pairs:
dsu.union(a, b) # swap করা যায় এমন index এক group
groups = defaultdict(list)
for i in range(n):
groups[dsu.find(i)].append(i) # প্রতি root-এ তার index গুলো জড়ো
res = list(s)
for idxs in groups.values():
chars = sorted(res[i] for i in idxs) # group-এর char sort
for i, c in zip(sorted(idxs), chars): # ছোট index <- ছোট char
res[i] = c
return "".join(res)
# ---- tests ----
assert smallest_string_with_swaps("dcab", [[0, 3], [1, 2]]) == "bacd"
assert smallest_string_with_swaps("dcab", [[0, 3], [1, 2], [0, 2]]) == "abcd"
assert smallest_string_with_swaps("cba", [[0, 1], [1, 2]]) == "abc"
assert smallest_string_with_swaps("abc", []) == "abc" # কোনো swap নেই
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `for a, b in pairs: dsu.union(a, b)` — প্রতিটা swap-pair দুটো index এক group-এ মেলায়; transitivity-তে সব reachable index এক হয়ে যায়।
- `groups[dsu.find(i)].append(i)` — প্রতিটা index-কে তার representative-এর bucket-এ ফেলি; এক root মানে এক group।
- `chars = sorted(res[i] for i in idxs)` — group-এর char-গুলো বর্ণানুক্রমে; এগুলোই smallest বিন্যাসের কাঁচামাল।
- `for i, c in zip(sorted(idxs), chars)` — index গুলোও sort করে, ছোট index-এ ছোট char বসাই — এটাই lexicographic minimum।
- `return "".join(res)` — সাজানো list থেকে চূড়ান্ত string।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
প্রথম test-এ {0,3}→'b','d' আর {1,2}→'a','c' বসে "bacd"। দ্বিতীয়টায় `[0,2]` সব index এক group করে; "dcab" sort হয়ে "abcd"। তৃতীয়টায় তিন index এক group, "cba"→"abc"। no-pairs case-এ প্রতিটা index একা group, কিছুই বদলায় না — "abc"। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n log n + P · α(n))** ≈ **O(n log n + P)** — P pair union (amortized near-constant), index bucket-এ ফেলা O(n), আর group-প্রতি sort মিলিয়ে মোট O(n log n)। sorting-ই dominating।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — `parent` + `size` array, groups dictionary, আর result list — সবই O(n)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- group-এর char sort করে **input-order** index-এ বসানো (sorted index নয়) — তখন ছোট char ছোট index-এ না-ও পড়তে পারে; index-ও sort করতে হবে।
- bucket করতে `parent[i]` ব্যবহার করা `find(i)`-এর বদলে — tree flat না হলে parent ≠ representative; classic DSU bug।
- প্রতি group আলাদা sort না করে পুরো string sort করা — তখন আলাদা group-এর char মিশে যায়, যা swap-এ অনুমোদিত নয়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি দুটো: এই tracker-এর grouping pattern (Pattern D) — swap relation = equivalence class; আর [../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md)-এর sorting — group-এর ভেতরে smallest বিন্যাস পেতে sort। DFS দিয়েও group বের করা যায়; কিন্তু "কোন index এক সাথে নড়ে?" DSU-তে সবচেয়ে সরাসরি, বিশেষত pair অনেক হলে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Accounts Merge (key share করে group, তারপর ভেতরে sort) —