Problem link ও উৎস
- **Original source:** Constraint থেকে graph বানিয়ে topological sort-এর classic প্রয়োগ
- **Platform:** LeetCode —
- **Topic:** graphs
- **Difficulty:** Hard
- **Pattern:** build constraints + topological sort (Kahn)
- **Basic idea inherited from:** Kahn's topological sort (এই tracker-এর #16, Course Schedule II)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা ভিনগ্রহের ভাষার কিছু word তোমাকে দেওয়া আছে, আর সেগুলো ওই ভাষার অভিধান-ক্রমে (dictionary order) **sorted** করে সাজানো — কিন্তু অক্ষরের ক্রম আমাদের ইংরেজির মতো নয়, অজানা। তোমাকে সেই অজানা অক্ষর-ক্রমটা বের করতে হবে: কোন অক্ষর আগে, কোনটা পরে। সম্ভব হলে অক্ষরগুলো সেই ক্রমে একটা string-এ ফেরত দাও; অসম্ভব (পরস্পরবিরোধী) হলে খালি string।
```text
words = [wrt, wrf, er, ett, rftt] (এই ভাষায় sorted)
পাশাপাশি word তুলনা করে অক্ষর-ক্রম বের হয়:
wrt vs wrf -> t আগে f
wrf vs er -> w আগে e
er vs ett -> r আগে t
ett vs rftt-> e আগে r
ক্রম: w e r t f -> "wertf"
```
### Input ও output {#8-example-input-and-output}
```text
Input : words = [wrt, wrf, er, ett, rftt]
Output: "wertf"
Input : words = [z, x]
Output: "zx"
Edge case (cycle, অসম্ভব): words = [z, x, z] -> ""
Edge case (bad prefix, sorted নয়): words = [abc, ab] -> ""
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তোমার হাতে কিছু "এর আগে ওটা" নিয়ম আছে — যেমন রান্নায়: "তেল গরম করার আগে কড়াই বসাও", "মশলা দেওয়ার আগে তেল গরম করো"। প্রতিটা নিয়ম দুই ধাপের মধ্যে একটা তীর। এখন তুমি এমন একটা পুরো ক্রম চাও যাতে কোনো নিয়ম ভাঙে না। তুমি শুরু করো সেই ধাপ দিয়ে যার আগে কিছু করার নেই (কড়াই বসানো), করে ফেলো, তারপর যে ধাপগুলোর সব পূর্বশর্ত মিটে গেছে সেগুলো — এভাবে। যদি নিয়মগুলো গোলকধাঁধা তৈরি করে (A-এর আগে B, B-এর আগে A), কোনো ক্রমই সম্ভব নয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **Kahn's topological sort**-এর উপর দাঁড়িয়ে (#16, Course Schedule II)। ওখানে course-এর prerequisite থেকে directed graph বানিয়ে valid ordering বের করা হয়েছিল; এখানে অক্ষরের precedence ("x আগে y") থেকে directed graph বানিয়ে valid অক্ষর-ক্রম বের করি। মূল মোচড়: graph টা তোমাকে দেওয়া হয়নি — তুমি **পাশাপাশি sorted word তুলনা করে** edge গুলো নিজে আবিষ্কার করবে। তারপর সব সেই চেনা Kahn।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic দুই অংশে। প্রথমত, dictionary order-এর সংজ্ঞা: দুটো পাশাপাশি word-এর প্রথম যে position-এ অক্ষর আলাদা, সেখানেই আগের word-এর অক্ষরটা ছোট (আগে আসে) — আর সেটাই **একমাত্র** তথ্য ওই জোড়া দেয়, বাকি position অর্থহীন। দ্বিতীয়ত, এই "আগে/পরে" সম্পর্কগুলো একটা partial order তৈরি করে, যাকে **directed graph**-এ ফেলে topological sort করলে একটা সঙ্গতিপূর্ণ total order পাওয়া যায়। যদি কোনো cycle থাকে (যেমন x আগে y, আবার y আগে x), তবে কোনো বৈধ ক্রম নেই। এক বিশেষ invalid কেস: প্রথম word দ্বিতীয়টার prefix হয়েও বড় ("abc" তারপর "ab") — এটা sorted নয়, তাই অসম্ভব।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
তিনটা: (১) একটা **dict (adjacency, set-of-neighbors)** — কোন অক্ষরের পর কোন অক্ষর আসে; (২) একটা **indegree dict** — প্রতিটা অক্ষরের কতগুলো "আগে আসতে হবে" constraint বাকি; (৩) Kahn চালাতে একটা **deque** — যেসব অক্ষরের indegree 0, তাদের queue। সাথে সব distinct অক্ষরের একটা সেট (indegree dict-এর key-ই সেটা দেয়)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
adjacency + indegree fit করে কারণ Kahn-এর পুরো কাজ — "indegree 0 অক্ষর বের করো, তাকে ক্রমে বসাও, তার neighbor-দের indegree কমাও"। deque fit করে কারণ ready (indegree 0) অক্ষরগুলো FIFO-তে process করলেই সঠিক ordering আসে, আর deque-এ push/pop O(1)। adjacency-তে `set` ব্যবহার fit করে কারণ একই (a→b) edge একাধিক word-জোড়া থেকে আসতে পারে — set duplicate এড়িয়ে indegree-এর ভুল গণনা ঠেকায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: সব অক্ষরের সম্ভাব্য permutation তৈরি করো, প্রতিটা permutation-কে অক্ষর-ক্রম ধরে যাচাই করো — এই ক্রমে word-গুলো কি সত্যিই sorted হয়? যে permutation সব word-জোড়াকে satisfy করে, সেটাই উত্তর।
```text
1) distinct অক্ষর বের করো
2) তাদের প্রতিটা permutation নাও
3) সেই ক্রম ধরে words sorted কিনা check করো
4) প্রথম যেটা মেলে, return
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
`c` টা distinct অক্ষর হলে permutation `c!` টা — factorial বিস্ফোরণ, সামান্য বেশি অক্ষরেই অগণিত। তার উপর প্রতিটা permutation যাচাই করতে আবার সব word-জোড়া মেলাতে হয়। মূল অপচয়: আমরা সব সম্ভাব্য ক্রম অন্ধভাবে চেষ্টা করছি, অথচ word-জোড়াগুলো সরাসরি অল্প কিছু precedence-নিয়ম বলে দেয় — সেই নিয়মগুলো একবার বের করে topological sort করলেই হয়, সব permutation দেখা লাগে না।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: পাশাপাশি দুটো sorted word শুধু **একটা** precedence তথ্য দেয় — প্রথম যে position-এ অক্ষর আলাদা, সেখানে আগের word-এর অক্ষর ছোট। এই কয়টা "x আগে y" নিয়মই পুরো অক্ষর-ক্রম নির্ধারণে যথেষ্ট, আর সেগুলো একটা directed graph-এর edge — topological sort করলেই বৈধ ক্রম।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
পাশাপাশি প্রতি জোড়া word ঘুরে প্রথম ভিন্ন অক্ষর `a, b` খোঁজো; edge `a → b` যোগ করো আর থামো (পরের position আর তথ্য দেয় না)। সাবধান: prefix-কেস — আগের word বড় অথচ পরেরটার prefix হলে ("abc" তারপর "ab") এটা অবৈধ, খালি string ফেরত। এরপর Kahn চালাও: indegree 0 অক্ষর queue-তে দাও, একে একে বের করে order-এ বসাও, neighbor-দের indegree কমাও; কেউ 0 হলে queue-তে দাও। শেষে যদি সব অক্ষর order-এ না আসে, তবে cycle ছিল → খালি string।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "অক্ষর-ক্রম বের করো" শুনে permutation খোঁজার দিকে যেও না; দেখো word-জোড়াগুলো আসলে "x আগে y" নিয়ম দিচ্ছে — মানে এটা edge। নিয়মগুলোকে graph বানিয়ে topological sort — চেনা #16-এ মিলিয়ে গেল। কঠিন অংশটা solving নয়, **edge গুলো সঠিকভাবে বের করা**।
### ছবিতে বোঝা {#7-visual-explanation}
`words = [wrt, wrf, er, ett, rftt]`। edge গুলো বের করি, তারপর Kahn:
```text
edges (পাশাপাশি word-এর প্রথম পার্থক্য থেকে):
wrt|wrf -> t->f
wrf|er -> w->e
er|ett -> r->t
ett|rftt-> e->r
indegree: w:0 e:1(w) r:1(e) t:1(r) f:1(t)
Kahn:
q=[w] -> নাও w, e-র indegree 0 -> q=[e]
নাও e, r-র indegree 0 -> q=[r]
নাও r, t-র indegree 0 -> q=[t]
নাও t, f-র indegree 0 -> q=[f]
নাও f
order = w e r t f -> "wertf"
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`words = [z, x]` (উত্তর "zx"):
1. `indegree = {z:0, x:0}` (সব distinct অক্ষর)।
2. জোড়া `(z, x)`: প্রথম position-এ `z != x` → edge `z → x`, `indegree[x] = 1`। break।
3. Kahn: indegree 0 হলো শুধু `z` → queue `[z]`।
4. pop `z`, order = `[z]`। `z`-এর neighbor `x`-এর indegree `1→0` → queue `[x]`।
5. pop `x`, order = `[z, x]`। queue খালি।
6. `len(order)=2 == distinct অক্ষর 2` → return `"zx"`।
`words = [z, x, z]`: edge `z→x` (z,x থেকে), edge `x→z` (x,z থেকে) → cycle। Kahn-এ কোনো indegree 0 নেই, order ছোট থেকে যায় → return `""`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import defaultdict, deque
def alien_order(words):
# প্রতিটা letter একটা node; পাশাপাশি word জোড়া থেকে precedence edge
adj = defaultdict(set)
indegree = {ch: 0 for w in words for ch in w}
for first, second in zip(words, words[1:]):
min_len = min(len(first), len(second))
# prefix problem: "abc" আগে "ab" এলে invalid
if len(first) > len(second) and first[:min_len] == second[:min_len]:
return ""
for a, b in zip(first, second):
if a != b:
if b not in adj[a]:
adj[a].add(b)
indegree[b] += 1
break # প্রথম পার্থক্যই একমাত্র constraint
# Kahn topo sort
queue = deque([c for c in indegree if indegree[c] == 0])
order = []
while queue:
ch = queue.popleft()
order.append(ch)
for nxt in adj[ch]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
if len(order) < len(indegree): # cycle -> অসম্ভব
return ""
return "".join(order)
# ---- tests ----
assert alien_order(["wrt", "wrf", "er", "ett", "rftt"]) == "wertf"
assert alien_order(["z", "x"]) == "zx"
assert alien_order(["z", "x", "z"]) == "" # cycle
assert alien_order(["abc", "ab"]) == "" # bad prefix
r = alien_order(["ab", "adc"])
assert r.index("b") < r.index("d") and set(r) == {"a", "b", "c", "d"}
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `indegree = {ch: 0 for ...}` — সব distinct অক্ষর শুরুতে indegree 0; এটাই node-সেটও বটে।
- `for first, second in zip(words, words[1:])` — পাশাপাশি প্রতি জোড়া word।
- `if len(first) > len(second) and first[:min_len]==second[:min_len]` — prefix-কেস ("abc" তারপর "ab") অবৈধ, খালি string।
- `for a, b in zip(first, second)` — দুই word অক্ষর-অক্ষর মেলাও।
- `if a != b:` ভেতরে — প্রথম পার্থক্যেই edge `a→b`; duplicate না হলে indegree বাড়াও; তারপর `break` (বাকি position অর্থহীন)।
- `queue = deque([c ... indegree[c]==0])` — Kahn-এর শুরু: যাদের আগে কিছু আসে না।
- `for nxt in adj[ch]: indegree[nxt]-=1` — অক্ষর বসানোর পর তার পরবর্তীদের একটা করে constraint মিটল; 0 হলে queue-তে।
- `if len(order) < len(indegree): return ""` — সব অক্ষর বসেনি মানে cycle, অসম্ভব।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`alien_order(["wrt","wrf","er","ett","rftt"])`: জোড়া তুলনায় edge বেরোয় `t→f, w→e, r→t, e→r`। indegree: w 0, বাকি 1 করে। Kahn w দিয়ে শুরু → e → r → t → f। order `wertf`, length 5 = distinct অক্ষর 5 → return `"wertf"`। cycle test (`z,x,z`)-এ indegree 0 কেউ নেই, order ছোট → `""`। prefix test (`abc,ab`)-এ early return `""`। বাকি assert pass, শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
পাশাপাশি word-এর প্রথম ভিন্ন অক্ষর থেকে edge, prefix-কেস invalid, তারপর Kahn — JS-এ `Map`/`Set`।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// words এই অজানা ভাষায় sorted; বৈধ অক্ষর-ক্রম return, অসম্ভব হলে ""
function alienOrder(words) {
const adj = new Map(); // অক্ষর -> Set of পরবর্তী অক্ষর
const indeg = new Map(); // অক্ষর -> বাকি "আগে আসতে হবে" সংখ্যা
for (const w of words) for (const ch of w) {
if (!adj.has(ch)) adj.set(ch, new Set());
if (!indeg.has(ch)) indeg.set(ch, 0);
}
for (let i = 0; i + 1 < words.length; i++) {
const first = words[i], second = words[i + 1];
const minLen = Math.min(first.length, second.length);
// prefix problem: "abc" আগে "ab" এলে invalid
if (first.length > second.length && first.slice(0, minLen) === second.slice(0, minLen)) {
return "";
}
for (let j = 0; j < minLen; j++) {
const a = first[j], b = second[j];
if (a !== b) {
if (!adj.get(a).has(b)) { adj.get(a).add(b); indeg.set(b, indeg.get(b) + 1); }
break; // প্রথম পার্থক্যই একমাত্র constraint
}
}
}
const queue = [];
for (const [ch, d] of indeg) if (d === 0) queue.push(ch);
let head = 0;
const order = [];
while (head < queue.length) {
const ch = queue[head++];
order.push(ch);
for (const nxt of adj.get(ch)) {
indeg.set(nxt, indeg.get(nxt) - 1);
if (indeg.get(nxt) === 0) queue.push(nxt);
}
}
if (order.length < indeg.size) return ""; // চক্র -> অসম্ভব
return order.join("");
}
// ---- test cases (example + edge) ----
assert(alienOrder(["wrt", "wrf", "er", "ett", "rftt"]) === "wertf", "classic");
assert(alienOrder(["z", "x"]) === "zx", "simple");
assert(alienOrder(["z", "x", "z"]) === "", "cycle"); // edge
assert(alienOrder(["abc", "ab"]) === "", "bad-prefix"); // edge
const r = alienOrder(["ab", "adc"]);
assert(r.indexOf("b") < r.indexOf("d") && new Set(r).size === 4, "partial-order");
console.log("সব JS test pass!");
```
> **JS টীকা:** adjacency-তে `Set` ব্যবহার করো (`Map