024 — Alien Dictionary

Source

• Original source: Constraint থেকে graph বানিয়ে topological sort-এর classic প্রয়োগ
• Platform: LeetCode — https://leetcode.com/problems/alien-dictionary/
• Topic: graphs
• Difficulty: Hard
• Pattern: build constraints + topological sort (Kahn)
• Basic idea inherited from: Kahn's topological sort (এই tracker-এর #16, Course Schedule II)

1. Problem in simple words

একটা ভিনগ্রহের ভাষার কিছু word তোমাকে দেওয়া আছে, আর সেগুলো ওই ভাষার অভিধান-ক্রমে (dictionary order) sorted করে সাজানো — কিন্তু অক্ষরের ক্রম আমাদের ইংরেজির মতো নয়, অজানা। তোমাকে সেই অজানা অক্ষর-ক্রমটা বের করতে হবে: কোন অক্ষর আগে, কোনটা পরে। সম্ভব হলে অক্ষরগুলো সেই ক্রমে একটা string-এ ফেরত দাও; অসম্ভব (পরস্পরবিরোধী) হলে খালি string।

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"

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-এর ভুল গণনা ঠেকায়।

6. Real-life analogy

ভাবো তোমার হাতে কিছু "এর আগে ওটা" নিয়ম আছে — যেমন রান্নায়: "তেল গরম করার আগে কড়াই বসাও", "মশলা দেওয়ার আগে তেল গরম করো"। প্রতিটা নিয়ম দুই ধাপের মধ্যে একটা তীর। এখন তুমি এমন একটা পুরো ক্রম চাও যাতে কোনো নিয়ম ভাঙে না। তুমি শুরু করো সেই ধাপ দিয়ে যার আগে কিছু করার নেই (কড়াই বসানো), করে ফেলো, তারপর যে ধাপগুলোর সব পূর্বশর্ত মিটে গেছে সেগুলো — এভাবে। যদি নিয়মগুলো গোলকধাঁধা তৈরি করে (A-এর আগে B, B-এর আগে A), কোনো ক্রমই সম্ভব নয়।

7. Visual explanation

words = [wrt, wrf, er, ett, rftt]। edge গুলো বের করি, তারপর Kahn:

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"

8. Example input and output

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] -> ""

9. Brute force thinking

প্রথম সরল চিন্তা: সব অক্ষরের সম্ভাব্য permutation তৈরি করো, প্রতিটা permutation-কে অক্ষর-ক্রম ধরে যাচাই করো — এই ক্রমে word-গুলো কি সত্যিই sorted হয়? যে permutation সব word-জোড়াকে satisfy করে, সেটাই উত্তর।

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 গুলো সঠিকভাবে বের করা।

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 ""।

15. Python solution

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, অসম্ভব।

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!।

18. Time complexity

O(C) যেখানে C = সব word-এর মোট অক্ষর-সংখ্যা — edge বের করতে word-জোড়া অক্ষর-অক্ষর মেলানো, আর Kahn-এ প্রতিটা node ও edge একবার করে। distinct অক্ষর সীমিত (alphabet-size), তাই কার্যত line।

19. Space complexity

O(1) alphabet হিসেবে / O(V+E) সাধারণভাবে — adjacency আর indegree distinct অক্ষর-সংখ্যায় সীমিত (alien alphabet ছোট), edge-ও তাই; queue-তেও সর্বোচ্চ সব distinct অক্ষর।

20. Common mistakes

• prefix-কেস (["abc","ab"]) handle না করা — এটা অবৈধ sorted, কিন্তু না ধরলে ভুলভাবে কোনো ক্রম ফেরত যায়।
• প্রথম পার্থক্যের পর break না দেওয়া — পরের position থেকেও edge যোগ করলে ভুল precedence ঢোকে।
• একই edge দুবার যোগ করে indegree বেশি গোনা — set ব্যবহার করে duplicate ঠেকাও।
• distinct অক্ষর সবগুলো node হিসেবে না নেওয়া (যেগুলো কোনো edge-এ নেই, তারাও output-এ থাকা উচিত)।
• cycle check (len(order) < len(indegree)) বাদ দেওয়া — পরস্পরবিরোধী input-এ ভুল আংশিক ক্রম ফেরত।

21. Which basic problem this inherits from

ভিত্তি: Kahn's topological sort (#16, Course Schedule II)। আটকে গেলে আগে #16 মনে করো — indegree 0 থেকে শুরু, neighbor-এর indegree কমাও, cycle হলে সব node বসে না। এই problem-এ কঠিন অংশটা শুধু আগে: graph-এর edge গুলো word-জোড়া থেকে বের করা। edge পেয়ে গেলে বাকিটা হুবহু #16।

22. Similar harder problems

• Course Schedule II (একই Kahn, edge সরাসরি দেওয়া) — https://leetcode.com/problems/course-schedule-ii/ (এই tracker-এর #16)
• Sequence Reconstruction (topo sort unique কিনা যাচাই) — https://leetcode.com/problems/sequence-reconstruction/
• Sort Items by Groups Respecting Dependencies (দুই স্তরের topo sort) — https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/

23. Pattern learned

Build constraints then topo sort: "এক বৈধ ক্রম বের করো" আর input পরোক্ষে "x আগে y" নিয়ম দিচ্ছে — নিয়মগুলো থেকে directed graph বানাও, তারপর Kahn; cycle থাকলে কোনো ক্রম নেই।

24. Final summary

ভবিষ্যতের আমাকে: "Alien Dictionary = পাশাপাশি word-এর প্রথম ভিন্ন অক্ষর থেকে edge (a→b, তারপর break), prefix-কেস invalid, তারপর চেনা Kahn; সব node না বসলে cycle = ''।" 'অজানা ক্রম/বৈধ ordering বের করো' আর pairwise constraint দেখলেই 'edge বানিয়ে topo sort' মনে পড়বে।

25. JavaScript solution (with test cases)

পাশাপাশি word-এর প্রথম ভিন্ন অক্ষর থেকে edge, prefix-কেস invalid, তারপর Kahn — JS-এ Map/Set।

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<char, Set>) — একই (a→b) edge একাধিক word-জোড়া থেকে এলে Set duplicate ঠেকিয়ে indegree-এর অতিরিক্ত গণনা আটকায়। সব distinct অক্ষরকে আগেই node বানাও (যেগুলো কোনো edge-এ নেই, তারাও output-এ থাকবে)। JS-এ string char-by-char পেতে for...of বা index দুটোই চলে।

26. TypeScript solution (with test cases)

function alienOrder(words: string[]): string {
  const adj: Map<string, Set<string>> = new Map();
  const indeg: Map<string, number> = 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: string = words[i], second: string = words[i + 1];
    const minLen: number = Math.min(first.length, second.length);
    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) {
        const nbrs = adj.get(a) as Set<string>;
        if (!nbrs.has(b)) { nbrs.add(b); indeg.set(b, (indeg.get(b) as number) + 1); }
        break;
      }
    }
  }
  const queue: string[] = [];
  for (const [ch, d] of indeg) if (d === 0) queue.push(ch);
  let head = 0;
  const order: string[] = [];
  while (head < queue.length) {
    const ch: string = queue[head++];
    for (const nxt of adj.get(ch) as Set<string>) {
      indeg.set(nxt, (indeg.get(nxt) as number) - 1);
      if (indeg.get(nxt) === 0) queue.push(nxt);
    }
    order.push(ch);
  }
  if (order.length < indeg.size) return "";
  return order.join("");
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(alienOrder(["wrt", "wrf", "er", "ett", "rftt"]), "wertf", "classic");
expect(alienOrder(["z", "x"]), "zx", "simple");
expect(alienOrder(["z", "x", "z"]), "", "cycle");
expect(alienOrder(["abc", "ab"]), "", "bad-prefix");
console.log("সব TS test pass!");

TS টীকা: Map<string, Set<string>> ও Map<string, number> typing করায় graph (অক্ষর→অক্ষর) আর indegree-গণনা আলাদা type-এ locked; strict mode-এ Map.get T | undefined দেয় বলে as Set<string>/as number দিয়ে narrow করতে হয় — এই বাধ্যতামূলক null-check-ই missing-key bug আগেভাগে ধরায়।

27. কোথায় কাজে লাগে (real-world use)

• Locale / custom collation: কোনো ভাষা বা ব্যবহারকারীর custom sort-order জানা থাকলে, sorted নমুনা থেকে সেই অক্ষর-ক্রম পুনরুদ্ধার করা।
• Version / ordering inference: কিছু sorted record থেকে অন্তর্নিহিত precedence নিয়ম (কোনটা আগে) বের করা — যেমন release tag বা priority order।
• Dependency from examples: সরাসরি নিয়ম না দিয়ে শুধু কিছু sorted/ordered উদাহরণ দিলে, তার থেকে "X আগে Y" constraint বের করে topological order।
• Schema / migration ordering: sorted নমুনা থেকে field বা step-এর আপেক্ষিক ক্রম অনুমান করা।
• Conflict detection: নমুনাগুলো পরস্পরবিরোধী (cycle) কিনা ধরা — অসম্ভব হলে "" এর মতো invalid signal।

মূল pattern: input পরোক্ষে "x আগে y" নিয়ম দিচ্ছে — সেই pairwise constraint থেকে edge বানিয়ে topological sort; cycle হলে কোনো ক্রম নেই।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।