These are the notes for DSA episode 88: two hard interview problems. Alien dictionary (LeetCode 269): a list of words is sorted in an unknown alphabet; trying every order of the letters is correct but times out with 14 letters (14! ≈ 87 billion orders). Each pair of neighbouring words gives one arrow from their first different letter; the arrows form a directed graph, and a topological sort (Kahn's algorithm, episode 51) reads the alphabet. A cycle or a word placed before its own prefix means no alphabet exists: return "". Minimum cost to cut a stick (LeetCode 1547): every cut costs the length of the piece being cut, so the order matters; cutting in the given order is wrong, trying every first cut is correct but times out with 100 cuts. A piece is fixed by its two ends, so sort the cuts, add 0 and n, and fill an interval DP table by gap, O(m³). Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).
The problems, in real life
| Real life | In code |
|---|---|
| Your little brother's secret words, written in a list sorted in his own alphabet | words[] sorted in an unknown order of letters |
| "Which letter comes first in his alphabet?" | return the letters in that order |
Two of his words that differ first at t and f |
an arrow t → f: t comes before f |
| A timber shop saw charges the length of the log on it | a cut costs the length of the piece being cut |
| You choose the order of the cuts | find the cheapest order |
Every word, from zero
- Lexicographic (dictionary) order: compare two words letter by letter; the first different letter decides; if one word runs out first, the shorter one comes first (
catbeforecats). - Prefix:
abis a prefix ofabcbecauseabcstarts withab. A word always comes after its own prefix. - Directed graph: dots called nodes (here: letters) joined by one-way arrows called edges (here: "comes before").
- In-degree: how many arrows point into a node: how many letters must come before it.
- Topological sort / topological order: an order of the nodes in which every arrow points forward.
- Kahn's algorithm: repeatedly take a node with in-degree 0, append it, and cross out its arrows (lowering the in-degree of the nodes they point to).
- Cycle: a path of arrows that comes back to where it started (
z → x → z). A graph with a cycle has no topological order. - Permutation: one ordering of a set of items;
kitems havek!(k factorial) orderings. - Recursion: a function that solves a problem by calling itself on smaller pieces.
- Subproblem: a smaller version of the problem whose answer helps solve the big one.
- Dynamic programming (DP): solve each subproblem once, store the answer in a table, and reuse it.
- Interval DP: DP where each subproblem is a range
[i, j]; bigger ranges are built from smaller ones (burst balloons, episode 74). - Time Limit Exceeded (TLE): the judge stopped the program because it ran longer than allowed.
Problem 1: alien dictionary (LeetCode 269)
You are given a list of words sorted lexicographically in an unknown alphabet of lowercase letters. Return a string of all the letters that appear, in an order consistent with the list. If no order works, return "". (Any valid order is accepted.)
| Input | Output |
|---|---|
["wrt","wrf","er","ett","rftt"] |
"wertf" |
["z","x"] |
"zx" |
["z","x","z"] |
"" (z before x and x before z) |
["abc","ab"] |
"" (a word before its own prefix) |
Obvious idea: try every order of the letters
Collect the letters, try every permutation, and check whether the list is sorted under it.
import java.util.*;
public class Main {
static String alienOrder(String[] words) {
StringBuilder letters = new StringBuilder();
for (String w : words)
for (char ch : w.toCharArray())
if (letters.indexOf("" + ch) < 0) letters.append(ch);
String r = tryAll(letters.toString(), "", words);
return r == null ? "" : r;
}
static String tryAll(String left, String order, String[] words) {
if (left.isEmpty()) return sortedBy(order, words) ? order : null;
for (int i = 0; i < left.length(); i++) {
String rest = left.substring(0, i) + left.substring(i + 1);
String r = tryAll(rest, order + left.charAt(i), words);
if (r != null) return r;
}
return null;
}
static boolean sortedBy(String order, String[] words) {
for (int i = 0; i + 1 < words.length; i++)
if (cmp(words[i], words[i + 1], order) > 0) return false;
return true;
}
static int cmp(String a, String b, String order) {
for (int k = 0; k < Math.min(a.length(), b.length()); k++)
if (a.charAt(k) != b.charAt(k))
return order.indexOf(a.charAt(k)) - order.indexOf(b.charAt(k));
return a.length() - b.length();
}
static void show(String... w) {
System.out.println(Arrays.toString(w) + " -> \"" + alienOrder(w) + "\"");
}
public static void main(String[] args) {
show("wrt", "wrf", "er", "ett", "rftt");
show("z", "x");
show("z", "x", "z");
show("abc", "ab");
}
}
Output (real):
[wrt, wrf, er, ett, rftt] -> "wertf"
[z, x] -> "zx"
[z, x, z] -> ""
[abc, ab] -> ""
Correct. Now 14 letters (a to n): the first word is anmlkjihgfedcb, followed by b, c, …, n, so the alphabet is abcdefghijklmn, but the brute force tries the letters in the order it first saw them and needs billions of orders to reach it.
import java.util.*;
public class Main {
static String alienOrder(String[] words) {
StringBuilder letters = new StringBuilder();
for (String w : words)
for (char ch : w.toCharArray())
if (letters.indexOf("" + ch) < 0) letters.append(ch);
String r = tryAll(letters.toString(), "", words);
return r == null ? "" : r;
}
static String tryAll(String left, String order, String[] words) {
if (left.isEmpty()) return sortedBy(order, words) ? order : null;
for (int i = 0; i < left.length(); i++) {
String rest = left.substring(0, i) + left.substring(i + 1);
String r = tryAll(rest, order + left.charAt(i), words);
if (r != null) return r;
}
return null;
}
static boolean sortedBy(String order, String[] words) {
for (int i = 0; i + 1 < words.length; i++)
if (cmp(words[i], words[i + 1], order) > 0) return false;
return true;
}
static int cmp(String a, String b, String order) {
for (int k = 0; k < Math.min(a.length(), b.length()); k++)
if (a.charAt(k) != b.charAt(k))
return order.indexOf(a.charAt(k)) - order.indexOf(b.charAt(k));
return a.length() - b.length();
}
public static void main(String[] args) {
String[] w = new String[14];
w[0] = "anmlkjihgfedcb";
for (int i = 1; i < 14; i++) w[i] = "" + (char) ('a' + i);
long t0 = System.nanoTime();
String order = alienOrder(w);
System.out.println(order + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
}
}
Result (real): Time Limit Exceeded (no output within 25 seconds). 14 letters have 14! = 87,178,291,200 orders.
Why it is slow
We guessed orders blindly and only used the list to say yes or no. But the list states the rules directly:
- In
wrt/wrf, the first different letters aretandf, so t comes before f. Letters after the first difference tell us nothing. - We only need neighbouring words: if word 1 ≤ word 2 and word 2 ≤ word 3, then word 1 ≤ word 3 follows. So
n − 1pairs give every rule.
The key insight: words become arrows, the alphabet is a topological order
| Pair | First difference | Arrow |
|---|---|---|
| wrt, wrf | t, f | t → f |
| wrf, er | w, e | w → e |
| er, ett | r, t | r → t |
| ett, rftt | e, r | e → r |
In-degrees: w 0, e 1, r 1, t 1, f 1. Kahn's algorithm takes w (in-degree 0), which frees e, then r, t, f: wertf.
Two traps:
- Cycle:
["z","x","z"]givesz → xandx → z. No letter ever reaches in-degree 0, so fewer letters are taken than exist: return"". - Prefix:
["abc","ab"]has no differing letter, so no arrow, yetabcbeforeabis impossible in every alphabet. The graph cannot notice; check it explicitly.
Solution in Java
import java.util.*;
public class Main {
static String alienOrder(String[] words) {
boolean[] seen = new boolean[26];
for (String w : words)
for (char ch : w.toCharArray()) seen[ch - 'a'] = true;
boolean[][] edge = new boolean[26][26];
int[] indeg = new int[26];
for (int i = 0; i + 1 < words.length; i++) {
String a = words[i], b = words[i + 1];
if (a.length() > b.length() && a.startsWith(b)) return "";
for (int k = 0; k < Math.min(a.length(), b.length()); k++) {
int x = a.charAt(k) - 'a', y = b.charAt(k) - 'a';
if (x != y) {
if (!edge[x][y]) { edge[x][y] = true; indeg[y]++; }
break;
}
}
}
Deque<Integer> q = new ArrayDeque<>();
int total = 0;
for (int c = 0; c < 26; c++)
if (seen[c]) { total++; if (indeg[c] == 0) q.add(c); }
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
int c = q.poll();
sb.append((char) ('a' + c));
for (int d = 0; d < 26; d++)
if (edge[c][d] && --indeg[d] == 0) q.add(d);
}
return sb.length() == total ? sb.toString() : "";
}
static void show(String... w) {
System.out.println(Arrays.toString(w) + " -> \"" + alienOrder(w) + "\"");
}
public static void main(String[] args) {
show("wrt", "wrf", "er", "ett", "rftt");
show("z", "x");
show("z", "x", "z");
show("abc", "ab");
}
}
Output (real):
[wrt, wrf, er, ett, rftt] -> "wertf"
[z, x] -> "zx"
[z, x, z] -> ""
[abc, ab] -> ""
The big test that timed out:
import java.util.*;
public class Main {
static String alienOrder(String[] words) {
boolean[] seen = new boolean[26];
for (String w : words)
for (char ch : w.toCharArray()) seen[ch - 'a'] = true;
boolean[][] edge = new boolean[26][26];
int[] indeg = new int[26];
for (int i = 0; i + 1 < words.length; i++) {
String a = words[i], b = words[i + 1];
if (a.length() > b.length() && a.startsWith(b)) return "";
for (int k = 0; k < Math.min(a.length(), b.length()); k++) {
int x = a.charAt(k) - 'a', y = b.charAt(k) - 'a';
if (x != y) {
if (!edge[x][y]) { edge[x][y] = true; indeg[y]++; }
break;
}
}
}
Deque<Integer> q = new ArrayDeque<>();
int total = 0;
for (int c = 0; c < 26; c++)
if (seen[c]) { total++; if (indeg[c] == 0) q.add(c); }
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
int c = q.poll();
sb.append((char) ('a' + c));
for (int d = 0; d < 26; d++)
if (edge[c][d] && --indeg[d] == 0) q.add(d);
}
return sb.length() == total ? sb.toString() : "";
}
public static void main(String[] args) {
String[] w = new String[14];
w[0] = "anmlkjihgfedcb";
for (int i = 1; i < 14; i++) w[i] = "" + (char) ('a' + i);
long t0 = System.nanoTime();
String order = alienOrder(w);
System.out.println(order + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
}
}
Output (real):
abcdefghijklmn, 0 ms
Notes on the code:
seen[]marks every letter, so a letter with no arrows still appears in the answer.edge[x][y]stops the same arrow from being counted twice inindeg[y](the same pair can appear many times).breakafter the first difference: later letters give no rule.sb.length() == totaldetects a cycle.
A real bug: no prefix check
import java.util.*;
public class Main {
static String alienOrder(String[] words) {
boolean[] seen = new boolean[26];
for (String w : words)
for (char ch : w.toCharArray()) seen[ch - 'a'] = true;
boolean[][] edge = new boolean[26][26];
int[] indeg = new int[26];
for (int i = 0; i + 1 < words.length; i++) {
String a = words[i], b = words[i + 1];
for (int k = 0; k < Math.min(a.length(), b.length()); k++) {
int x = a.charAt(k) - 'a', y = b.charAt(k) - 'a';
if (x != y) {
if (!edge[x][y]) { edge[x][y] = true; indeg[y]++; }
break;
}
}
}
Deque<Integer> q = new ArrayDeque<>();
int total = 0;
for (int c = 0; c < 26; c++)
if (seen[c]) { total++; if (indeg[c] == 0) q.add(c); }
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
int c = q.poll();
sb.append((char) ('a' + c));
for (int d = 0; d < 26; d++)
if (edge[c][d] && --indeg[d] == 0) q.add(d);
}
return sb.length() == total ? sb.toString() : "";
}
static void show(String... w) {
System.out.println(Arrays.toString(w) + " -> \"" + alienOrder(w) + "\"");
}
public static void main(String[] args) {
show("z", "x", "z");
show("abc", "ab");
}
}
Output (real):
[z, x, z] -> ""
[abc, ab] -> "abc"
Without arrows every letter has in-degree 0, so Kahn's algorithm happily returns "abc", a confident wrong answer.
Problem 2: minimum cost to cut a stick (LeetCode 1547)
A wooden stick of length n is marked at positions cuts[]. Each cut costs the length of the piece being cut. You may perform the cuts in any order. Return the minimum total cost.
| Input | Output |
|---|---|
n = 7, cuts = [1, 3, 4, 5] |
16 |
n = 9, cuts = [5, 6, 1, 4, 2] |
22 |
n = 10, cuts = [3] |
10 |
n = 5, cuts = [1, 2, 3, 4] |
12 |
Obvious idea 1: cut in the given order
A TreeSet holds the cuts made so far; the piece around a new cut runs from the nearest cut below (lower) to the nearest cut above (higher).
import java.util.*;
public class Main {
static int minCost(int n, int[] cuts) {
TreeSet<Integer> made = new TreeSet<>(List.of(0, n));
int cost = 0;
for (int c : cuts) {
cost += made.higher(c) - made.lower(c);
made.add(c);
}
return cost;
}
public static void main(String[] args) {
System.out.println(minCost(7, new int[]{1, 3, 4, 5}));
System.out.println(minCost(9, new int[]{5, 6, 1, 4, 2}));
}
}
Output (real):
20
25
Wrong: 20 and 25 instead of 16 and 22. Cutting at 1 first pays for the whole 7, then 6 for the rest.
Obvious idea 2: try every first cut (recursion)
To finish the piece l..r, try each cut inside it as the first one: pay r − l, then finish both sides the cheapest way. No cut inside costs 0.
import java.util.*;
public class Main {
static int cost(int l, int r, int[] cuts) {
int best = Integer.MAX_VALUE;
for (int c : cuts)
if (l < c && c < r)
best = Math.min(best, (r - l) + cost(l, c, cuts) + cost(c, r, cuts));
return best == Integer.MAX_VALUE ? 0 : best;
}
static int minCost(int n, int[] cuts) {
return cost(0, n, cuts);
}
public static void main(String[] args) {
System.out.println(minCost(7, new int[]{1, 3, 4, 5}));
System.out.println(minCost(9, new int[]{5, 6, 1, 4, 2}));
System.out.println(minCost(10, new int[]{3}));
System.out.println(minCost(5, new int[]{1, 2, 3, 4}));
}
}
Output (real):
16
22
10
12
Correct. Now a log of 1,000,000 mm with 100 cuts:
import java.util.*;
public class Main {
static int cost(int l, int r, int[] cuts) {
int best = Integer.MAX_VALUE;
for (int c : cuts)
if (l < c && c < r)
best = Math.min(best, (r - l) + cost(l, c, cuts) + cost(c, r, cuts));
return best == Integer.MAX_VALUE ? 0 : best;
}
static int minCost(int n, int[] cuts) {
return cost(0, n, cuts);
}
public static void main(String[] args) {
int[] cuts = new int[100];
for (int i = 0; i < 100; i++) cuts[i] = (i * 37 % 100 + 1) * 9973;
long t0 = System.nanoTime();
int best = minCost(1_000_000, cuts);
System.out.println(best + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
}
}
Result (real): Time Limit Exceeded. The number of cut orders grows exponentially with m.
Why it is slow, and the key insight
Cutting at 3 then 4 leaves the piece 4..7; cutting at 4 first leaves the same piece 4..7. The recursion solves it again every time. But:
- After the first cut, the two sides are independent.
- Every piece is fixed by its two ends, and an end is always
0,nor a cut. Withmcuts there are only about(m + 2)²pieces.
Sort the cuts and add the ends: p = [0, 1, 3, 4, 5, 7].
dp[i][j] = cheapest cost to make every cut strictly between p[i] and p[j]
dp[i][i+1] = 0 (no cut inside)
dp[i][j] = p[j] - p[i] + min over i < k < j of dp[i][k] + dp[k][j]
fill by gap = j - i, from 2 upward
The table for n = 7, cuts = [1, 3, 4, 5] (row = gap, column = start i):
| gap | i = 0 | i = 1 | i = 2 | i = 3 |
|---|---|---|---|---|
| 2 | dp(0,2) = 3 | dp(1,3) = 3 | dp(2,4) = 2 | dp(3,5) = 3 |
| 3 | dp(0,3) = 4 + min(0+3, 3+0) = 7 | dp(1,4) = 6 | dp(2,5) = 6 | |
| 4 | dp(0,4) = 5 + min(0+6, 3+2, 7+0) = 10 | dp(1,5) = 12 | ||
| 5 | dp(0,5) = 7 + min(0+12, 3+6, 7+3, 10+0) = 16 |
The best first cut of the whole log is at p[2] = 3; then 1, then 4 and 5.
Solution in Java
import java.util.*;
public class Main {
static int minCost(int n, int[] cuts) {
int m = cuts.length;
int[] p = new int[m + 2];
for (int i = 0; i < m; i++) p[i + 1] = cuts[i];
p[m + 1] = n;
Arrays.sort(p);
int[][] dp = new int[m + 2][m + 2];
for (int gap = 2; gap <= m + 1; gap++)
for (int i = 0; i + gap <= m + 1; i++) {
int j = i + gap;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i + 1; k < j; k++)
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
dp[i][j] += p[j] - p[i];
}
return dp[0][m + 1];
}
public static void main(String[] args) {
System.out.println(minCost(7, new int[]{1, 3, 4, 5}));
System.out.println(minCost(9, new int[]{5, 6, 1, 4, 2}));
System.out.println(minCost(10, new int[]{3}));
System.out.println(minCost(5, new int[]{1, 2, 3, 4}));
}
}
Output (real):
16
22
10
12
The 100 cuts that timed out:
import java.util.*;
public class Main {
static int minCost(int n, int[] cuts) {
int m = cuts.length;
int[] p = new int[m + 2];
for (int i = 0; i < m; i++) p[i + 1] = cuts[i];
p[m + 1] = n;
Arrays.sort(p);
int[][] dp = new int[m + 2][m + 2];
for (int gap = 2; gap <= m + 1; gap++)
for (int i = 0; i + gap <= m + 1; i++) {
int j = i + gap;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i + 1; k < j; k++)
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
dp[i][j] += p[j] - p[i];
}
return dp[0][m + 1];
}
public static void main(String[] args) {
int[] cuts = new int[100];
for (int i = 0; i < 100; i++) cuts[i] = (i * 37 % 100 + 1) * 9973;
long t0 = System.nanoTime();
int best = minCost(1_000_000, cuts);
System.out.println(best + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
}
}
Output (real):
6730729, 8 ms
A real bug: forgot to sort
import java.util.*;
public class Main {
static int minCost(int n, int[] cuts) {
int m = cuts.length;
int[] p = new int[m + 2];
for (int i = 0; i < m; i++) p[i + 1] = cuts[i];
p[m + 1] = n;
int[][] dp = new int[m + 2][m + 2];
for (int gap = 2; gap <= m + 1; gap++)
for (int i = 0; i + gap <= m + 1; i++) {
int j = i + gap;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i + 1; k < j; k++)
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
dp[i][j] += p[j] - p[i];
}
return dp[0][m + 1];
}
public static void main(String[] args) {
System.out.println(minCost(7, new int[]{1, 3, 4, 5}));
System.out.println(minCost(9, new int[]{5, 6, 1, 4, 2}));
}
}
Output (real):
16
2
The first example has sorted cuts, so it still works. In the second, neighbours in the array are not neighbours on the stick, and p[j] − p[i] is not a real length (some are negative): 2 instead of 22.
The same solutions in C++
#include <bits/stdc++.h>
using namespace std;
string alienOrder(const vector<string>& words) {
bool seen[26] = {}, edge[26][26] = {};
int indeg[26] = {};
for (auto& w : words) for (char ch : w) seen[ch - 'a'] = true;
for (size_t i = 0; i + 1 < words.size(); i++) {
const string &a = words[i], &b = words[i + 1];
if (a.size() > b.size() && a.compare(0, b.size(), b) == 0) return "";
for (size_t k = 0; k < min(a.size(), b.size()); k++) {
int x = a[k] - 'a', y = b[k] - 'a';
if (x != y) {
if (!edge[x][y]) { edge[x][y] = true; indeg[y]++; }
break;
}
}
}
queue<int> q; int total = 0;
for (int c = 0; c < 26; c++) if (seen[c]) { total++; if (indeg[c] == 0) q.push(c); }
string res;
while (!q.empty()) {
int c = q.front(); q.pop();
res += char('a' + c);
for (int d = 0; d < 26; d++)
if (edge[c][d] && --indeg[d] == 0) q.push(d);
}
return (int)res.size() == total ? res : "";
}
int minCost(int n, vector<int> cuts) {
vector<int> p = {0, n};
p.insert(p.end(), cuts.begin(), cuts.end());
sort(p.begin(), p.end());
int s = p.size();
vector<vector<int>> dp(s, vector<int>(s, 0));
for (int gap = 2; gap < s; gap++)
for (int i = 0; i + gap < s; i++) {
int j = i + gap, best = INT_MAX;
for (int k = i + 1; k < j; k++) best = min(best, dp[i][k] + dp[k][j]);
dp[i][j] = best + p[j] - p[i];
}
return dp[0][s - 1];
}
int main() {
vector<vector<string>> tests = {{"wrt", "wrf", "er", "ett", "rftt"}, {"z", "x"}, {"z", "x", "z"}, {"abc", "ab"}};
for (auto& t : tests) cout << "\"" << alienOrder(t) << "\"\n";
cout << minCost(7, {1, 3, 4, 5}) << "\n" << minCost(9, {5, 6, 1, 4, 2}) << "\n";
cout << minCost(10, {3}) << "\n" << minCost(5, {1, 2, 3, 4}) << "\n";
vector<int> big(100);
for (int i = 0; i < 100; i++) big[i] = (i * 37 % 100 + 1) * 9973;
cout << minCost(1000000, big) << "\n";
}
Output (real):
"wertf"
"zx"
""
""
16
22
10
12
6730729
The same solutions in Python
from collections import deque
def alien_order(words):
letters = {ch for w in words for ch in w}
edges = {ch: set() for ch in letters}
indeg = {ch: 0 for ch in letters}
for a, b in zip(words, words[1:]):
if len(a) > len(b) and a.startswith(b):
return ""
for x, y in zip(a, b):
if x != y:
if y not in edges[x]:
edges[x].add(y)
indeg[y] += 1
break
q = deque(sorted(c for c in letters if indeg[c] == 0))
res = []
while q:
c = q.popleft()
res.append(c)
for d in sorted(edges[c]):
indeg[d] -= 1
if indeg[d] == 0:
q.append(d)
return "".join(res) if len(res) == len(letters) else ""
def min_cost(n, cuts):
p = sorted([0, n] + cuts)
s = len(p)
dp = [[0] * s for _ in range(s)]
for gap in range(2, s):
for i in range(s - gap):
j = i + gap
dp[i][j] = p[j] - p[i] + min(dp[i][k] + dp[k][j] for k in range(i + 1, j))
return dp[0][s - 1]
for t in (["wrt", "wrf", "er", "ett", "rftt"], ["z", "x"], ["z", "x", "z"], ["abc", "ab"]):
print(f'"{alien_order(t)}"')
print(min_cost(7, [1, 3, 4, 5]), min_cost(9, [5, 6, 1, 4, 2]))
print(min_cost(10, [3]), min_cost(5, [1, 2, 3, 4]))
print(min_cost(1_000_000, [(i * 37 % 100 + 1) * 9973 for i in range(100)]))
Output (real):
"wertf"
"zx"
""
""
16 22
10 12
6730729
Complexity
k = number of distinct letters, C = total letters in all words, m = number of cuts.
| Problem | Approach | Time | Extra memory | Big test |
|---|---|---|---|---|
| Alien dictionary | every order of the letters | O(k! · C) | O(k) | 14 letters: Time Limit Exceeded |
| Alien dictionary | arrows + Kahn's algorithm | O(C + 26²) | O(26²) | instant |
| Cut a stick | given order | O(m log m) | O(m) | wrong |
| Cut a stick | every first cut (recursion) | exponential | O(m) stack | 100 cuts: Time Limit Exceeded |
| Cut a stick | interval DP | O(m³) | O(m²) | a few ms |
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| No prefix check | [abc, ab] -> "abc" |
no arrows, every letter ready | if (a.length() > b.length() && a.startsWith(b)) return ""; |
No break after the first difference |
[ab, ba] -> "" (should be "ab") |
later letters give no rule: b → a is false |
stop at the first difference |
| Adding only letters that have arrows | letters missing from the answer | a lonely letter has no edge | mark every letter in seen[] |
| Counting a repeated arrow without a table | in-degrees wrong unless every copy is crossed out too | the same pair appears again | edge[x][y] table or a set |
| Comparing every pair of words | correct but O(n²) pairs | neighbours already give every rule | compare words[i] and words[i + 1] |
| Cutting in the given order | 20, not 16 |
the order changes the bill | try every first cut (DP) |
Forgot Arrays.sort(p) |
2, not 22 |
array neighbours are not stick neighbours | sort, with 0 and n added |
Filling the table by i from 0 upward |
reads dp[k][j] before it is filled (still 0) |
a big piece needs smaller ones first | loop over gap, or i from high to low |
Mini project: read your brother's diary
Given his sorted word list, recover his alphabet, then sort your own words his way (so he can read your replies).
import java.util.*;
public class Main {
public static void main(String[] args) {
String[] his = {"pip", "pik", "ipk", "kip", "kki"};
String order = alienOrder(his);
System.out.println("alphabet: " + order);
int[] rank = new int[26];
for (int i = 0; i < order.length(); i++) rank[order.charAt(i) - 'a'] = i;
List<String> mine = new ArrayList<>(List.of("kp", "pp", "ik", "pi", "ki"));
mine.sort((a, b) -> {
for (int k = 0; k < Math.min(a.length(), b.length()); k++)
if (a.charAt(k) != b.charAt(k)) return rank[a.charAt(k) - 'a'] - rank[b.charAt(k) - 'a'];
return a.length() - b.length();
});
System.out.println("sorted his way: " + mine);
}
static String alienOrder(String[] words) {
boolean[] seen = new boolean[26];
for (String w : words)
for (char ch : w.toCharArray()) seen[ch - 'a'] = true;
boolean[][] edge = new boolean[26][26];
int[] indeg = new int[26];
for (int i = 0; i + 1 < words.length; i++) {
String a = words[i], b = words[i + 1];
if (a.length() > b.length() && a.startsWith(b)) return "";
for (int k = 0; k < Math.min(a.length(), b.length()); k++) {
int x = a.charAt(k) - 'a', y = b.charAt(k) - 'a';
if (x != y) {
if (!edge[x][y]) { edge[x][y] = true; indeg[y]++; }
break;
}
}
}
Deque<Integer> q = new ArrayDeque<>();
int total = 0;
for (int c = 0; c < 26; c++)
if (seen[c]) { total++; if (indeg[c] == 0) q.add(c); }
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
int c = q.poll();
sb.append((char) ('a' + c));
for (int d = 0; d < 26; d++)
if (edge[c][d] && --indeg[d] == 0) q.add(d);
}
return sb.length() == total ? sb.toString() : "";
}
}
Output (real):
alphabet: pik
sorted his way: [pp, pi, ik, kp, ki]
Extend it: if the alphabet is not unique (two letters with in-degree 0 at the same time), print every possible alphabet with backtracking.
Practice
1. Verifying an Alien Dictionary (LeetCode 953): given the alphabet order, is the list sorted?
2. Minimum Score Triangulation of Polygon (LeetCode 1039): another interval DP: dp[i][j] = min over k of dp[i][k] + v[i]·v[k]·v[j] + dp[k][j].
3. The most expensive order to cut the stick (change min to max).
Solutions
import java.util.*;
public class Main {
static boolean isAlienSorted(String[] words, String order) {
int[] rank = new int[26];
for (int i = 0; i < 26; i++) rank[order.charAt(i) - 'a'] = i;
for (int i = 0; i + 1 < words.length; i++) {
String a = words[i], b = words[i + 1];
int k = 0;
while (k < a.length() && k < b.length() && a.charAt(k) == b.charAt(k)) k++;
if (k == b.length() && k < a.length()) return false;
if (k < a.length() && rank[a.charAt(k) - 'a'] > rank[b.charAt(k) - 'a']) return false;
}
return true;
}
static int minScoreTriangulation(int[] v) {
int n = v.length;
int[][] dp = new int[n][n];
for (int gap = 2; gap < n; gap++)
for (int i = 0; i + gap < n; i++) {
int j = i + gap;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i + 1; k < j; k++)
dp[i][j] = Math.min(dp[i][j], dp[i][k] + v[i] * v[k] * v[j] + dp[k][j]);
}
return dp[0][n - 1];
}
static int maxCost(int n, int[] cuts) {
int m = cuts.length;
int[] p = new int[m + 2];
for (int i = 0; i < m; i++) p[i + 1] = cuts[i];
p[m + 1] = n;
Arrays.sort(p);
int[][] dp = new int[m + 2][m + 2];
for (int gap = 2; gap <= m + 1; gap++)
for (int i = 0; i + gap <= m + 1; i++) {
int j = i + gap;
for (int k = i + 1; k < j; k++)
dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j]);
dp[i][j] += p[j] - p[i];
}
return dp[0][m + 1];
}
public static void main(String[] args) {
System.out.println(isAlienSorted(new String[]{"hello", "leetcode"}, "hlabcdefgijkmnopqrstuvwxyz"));
System.out.println(isAlienSorted(new String[]{"word", "world", "row"}, "worldabcefghijkmnpqstuvxyz"));
System.out.println(isAlienSorted(new String[]{"apple", "app"}, "abcdefghijklmnopqrstuvwxyz"));
System.out.println(minScoreTriangulation(new int[]{1, 2, 3}));
System.out.println(minScoreTriangulation(new int[]{3, 7, 4, 5}));
System.out.println(minScoreTriangulation(new int[]{1, 3, 1, 4, 1, 5}));
System.out.println(maxCost(7, new int[]{1, 3, 4, 5}));
}
}
Output (real):
true
false
false
6
144
13
20
Quick quiz
What does alienOrder(["ba", "bc", "ac", "cab"]) return? A) "bac" B) "abc" C) "" D) "cab"
Answer
A. ba, bc: a before c. bc, ac: b before a. ac, cab: a before c. Arrows b → a → c, so the order is bac (real output: [ba, bc, ac, cab] -> "bac").
Interview questions
- Why are only neighbouring words compared? Sorted order is transitive: word 1 ≤ word 2 ≤ word 3 already implies word 1 ≤ word 3.
- How do you detect that no alphabet exists? A cycle (Kahn's algorithm takes fewer letters than exist) or a longer word placed before its own prefix.
- Can you use DFS instead of Kahn's algorithm? Yes: DFS with three colours (unvisited, in progress, done), reverse post-order; a back edge to an "in progress" letter is a cycle.
- Is the alphabet unique? Only if the queue never holds two letters at once; otherwise several orders are valid.
- Why does cutting the stick need DP and not greedy? Greedy rules (given order, middle first, smallest piece first) fail on some inputs; the first cut decides the sizes of everything after it.
- Why sort the cuts and add 0 and n? So
p[i]..p[j]is a real piece with real lengthp[j] − p[i], and neighbours in the array are neighbours on the stick. - Time and space? Alien dictionary O(C + 26²) time, O(26²) memory; cutting the stick O(m³) time, O(m²) memory.
Glossary
| Term | Meaning |
|---|---|
| Lexicographic order | Dictionary order: first different letter decides, shorter word first if one is a prefix |
| Prefix | The start of a word: ab is a prefix of abc |
| Directed graph | Nodes joined by one-way arrows (edges) |
| Node / edge | A point (a letter) / an arrow between two points |
| In-degree | Number of arrows coming into a node |
| Topological sort | An order where every arrow points forward |
| Kahn's algorithm | Topological sort by repeatedly taking in-degree-0 nodes |
| Cycle | Arrows leading back to the start; no topological order exists |
| Permutation | One ordering of items; k items have k! |
| Recursion | A function calling itself on smaller inputs |
| Subproblem | A smaller version of the problem |
| Dynamic programming | Solve each subproblem once and store the answer |
| Interval DP | DP over ranges [i, j], filled from small ranges to big |
| Time Limit Exceeded | The program ran longer than the judge allows |
Summary
- Alien dictionary: each pair of neighbouring words gives at most one arrow, from the first different letter.
- The alphabet is a topological order of those arrows (Kahn's algorithm); a cycle or a word before its own prefix means
"". - Mark every letter, count each arrow once, and stop at the first difference.
- Cutting a stick: the order of cuts changes the cost; a piece is fixed by its two ends.
- Sort the cuts, add
0andn, and filldp[i][j] = p[j] − p[i] + min dp[i][k] + dp[k][j]by gap: O(m³). - Next episode: how to crack any problem: recognising the pattern.