DSA-105 · Infer first-difference inequalities, then choose the smallest legal topological prefix
Alien Dictionary
Advanced · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 24249 deterministic checks. Learner drafts are not executed.
Understand the problem
Given words claimed to be sorted in an unknown alphabet, infer the lexicographically smallest valid order of all observed letters. Return Optional.empty() when the ordering is impossible.
- words is a nonnull array of nonnull lowercase-ASCII Strings. Empty words, repeated words, and an empty array are valid. At most 100,000 words and 100,000 total characters are size preconditions. Null array/entry throws NullPointerException; any non-a..z character throws IllegalArgumentException. Validate every entry before any semantic shortcut.
- Include exactly the observed distinct letters, even those not constrained by a word comparison. The smallest answer is measured by ordinary a..z order among all valid alien alphabet permutations; it is an explicit tie-break, not an assumption about the unknown alphabet.
- Adjacent words impose only their first differing-letter inequality. A longer word before its exact prefix is impossible regardless of alphabet. Repeated inequalities are one graph edge. Return Optional.of("") for no observed letters and Optional.empty() for prefix conflict or cycle. Preserve the input array, its order, and original String references.
Examples
Input:
[wrt,wrf,er,ett,rftt]
Output:Optional.of("wertf")First differences imply t<f, w<e, r<t, and e<r. The chain includes every observed letter.
Input:
[za,zb,ca,cb]
Output:Optional.of("abzc")a<b is observed twice but counted once; z<c is independent. A min-queue chooses a, then newly ready b before z.
Input:
[abc,ab]
Output:Optional.empty()Changing character ranks cannot make a longer word precede its own prefix.
Input:
["",""]
Output:Optional.of("")There are no observed symbols and no contradictory word order.
Before you start
- Lexicographic word comparison and prefix rules
- Topological constraints and priority queue ordering
Recognize the structure
Word order is evidence about a partial order on letters, not a request to sort the given words. First infer necessary inequalities from neighboring words; then test and linearize that graph. Prefix conflicts need a separate check because they produce no differing-character edge.
Try before revealing
Hint 1
Compare neighboring words, stopping at the first different letter.
Hint 2
Check the longer-before-prefix contradiction and deduplicate inequalities.
Hint 3
Include isolated letters and repeatedly emit the smallest zero-indegree symbol.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Enumerate complete observed-letter permutations
Try every permutation of the observed alphabet in ordinary character order. At a leaf, rank its letters and compare every adjacent input word in full, using the prefix-length rule when no differing character exists. The first valid permutation is the smallest. This compiling baseline is factorial and is exercised only on bounded alphabets, not the 26-letter worst case.
Improve the baseline
Register symbols and compare neighboring words
Scan all characters so isolated letters are retained. For each adjacent pair, advance through the common prefix; reject a longer-before-shorter prefix, otherwise add only the first inequality.
Keep graph and indegree deduplication consistent
A boolean edge matrix records whether from→to already exists. Increment the destination degree only for a new inequality; repeated evidence does not add another prerequisite.
Use a minimum ready frontier
Place every observed zero-indegree symbol in a min-priority queue. Emit its least symbol, scan its true outgoing edges, and admit neighbors on transition to zero. A short final output means a cycle; no symbols means a successful empty String.
Why it is correct
Adjacent comparisons are sufficient
The first differing symbol determines a pair of words; later symbols cannot constrain that comparison. If every adjacent pair is nondecreasing under the inferred alphabet, transitivity makes the full input nondecreasing. Prefix violations are impossible under every rank assignment.
Topological outputs exactly satisfy the evidence
Every emitted symbol has all incoming inequalities discharged; a complete emitted permutation respects all inferred comparisons. A residual cycle makes such a permutation impossible. The observed-symbol set ensures neither missing letters nor invented letters.
Greedy smallest-prefix argument
Any legal next symbol must currently have zero indegree. Choosing the smallest such symbol cannot block a solution: removing any zero source leaves a DAG when one exists. Against a different valid order, the first differing choice is smaller, proving global lexicographic minimality. Trace edge-release states include pending inequalities of the just-emitted symbol.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.*;
public final class Solution {
private static void validate(String[] words) {
Objects.requireNonNull(words,"words");for(String word:words){Objects.requireNonNull(word,"word");for(int i=0;i<word.length();i++)if(word.charAt(i)<'a'||word.charAt(i)>'z')throw new IllegalArgumentException("expected lowercase ASCII");}
}
public static Optional<String> alienOrder(String[] words) {
validate(words);boolean[] present=new boolean[26];boolean[][] edge=new boolean[26][26];int[] indegree=new int[26];int count=0;
for(String word:words)for(int i=0;i<word.length();i++){int v=word.charAt(i)-'a';if(!present[v]){present[v]=true;count++;}}
for(int i=1;i<words.length;i++) {
String a=words[i-1],b=words[i];int p=0;while(p<Math.min(a.length(),b.length())&&a.charAt(p)==b.charAt(p))p++;
if(p==Math.min(a.length(),b.length())){if(a.length()>b.length())return Optional.empty();continue;}
int from=a.charAt(p)-'a',to=b.charAt(p)-'a';if(!edge[from][to]){edge[from][to]=true;indegree[to]++;}
}
PriorityQueue<Integer> ready=new PriorityQueue<>();for(int v=0;v<26;v++)if(present[v]&&indegree[v]==0)ready.add(v);
StringBuilder result=new StringBuilder();
while(!ready.isEmpty()) {
int v=ready.remove();result.append((char)('a'+v));
for(int next=0;next<26;next++)if(edge[v][next]&&--indegree[next]==0)ready.add(next);
}
return result.length()==count?Optional.of(result.toString()):Optional.empty();
}
public static Optional<String> baseline(String[] words) {
validate(words);boolean[] present=new boolean[26];for(String word:words)for(int i=0;i<word.length();i++)present[word.charAt(i)-'a']=true;
int count=0;for(boolean value:present)if(value)count++;return enumerate(words,present,new boolean[26],new StringBuilder(),count);
}
private static Optional<String> enumerate(String[] words,boolean[] present,boolean[] used,StringBuilder order,int count) {
if(order.length()==count){int[] rank=new int[26];for(int i=0;i<count;i++)rank[order.charAt(i)-'a']=i;for(int i=1;i<words.length;i++){String a=words[i-1],b=words[i];int p=0;while(p<Math.min(a.length(),b.length())&&a.charAt(p)==b.charAt(p))p++;if(p==Math.min(a.length(),b.length())){if(a.length()>b.length())return Optional.empty();}else if(rank[a.charAt(p)-'a']>rank[b.charAt(p)-'a'])return Optional.empty();}return Optional.of(order.toString());}
for(int v=0;v<26;v++)if(present[v]&&!used[v]){used[v]=true;order.append((char)('a'+v));Optional<String> answer=enumerate(words,present,used,order,count);if(answer.isPresent())return answer;order.setLength(order.length()-1);used[v]=false;}return Optional.empty();
}
}
Read the meaningful blocks
Prefix failures return an absent Optional
An invalid alphabet character is malformed input and throws; abc before ab is well-formed data with no solution. Optional.of("") is deliberately distinct from absence.
A boolean matrix models distinct inequalities
There are at most A=26 symbols. Matrix membership makes deduplication exact; scanning A neighbors per emitted symbol is part of the implementation cost.
Priority chips are a sorted teaching view
Java PriorityQueue iteration is not sorted. Walkthroughs display removal priority, while the actual method repeatedly calls remove. New zeroes compete immediately with older entries.
Complexity
Let W be word occurrences, T total input characters, A=26 alphabet capacity, V observed letters, and E distinct inferred edges. Main time is O(W+T+A²+E+V log(V+1)); adjacent common-prefix work is bounded by O(T+W), and the VA neighbor scans fit A². Auxiliary storage is O(A²+V), with O(V) returned text. A is fixed here, but its matrix/scan costs are stated explicitly.
The baseline has factorial worst-case time O(V!·(W+T+A+V+1)) and O(A+V+1) peak auxiliary rank/used/recursion/builder space beyond immutable inputs and output. The main method is iterative; baseline testing stays at small V because a contradictory 26-symbol input can force infeasible enumeration.
Exact-state walkthroughs
Reveal normal and boundary traces
Infer a constrained five-letter alphabet
Input: ["wrt","wrf","er","ett","rftt"] · Optional smallest alphabet: Optional.of("wertf")
Step 1 of 17: Register every observed symbol, including unconstrained letters.
Only observed lowercase-ASCII symbols belong in the answer. Validation scans the entire input before any semantic failure.
Phase: initial.
Input words — exact order; quotes preserve empty words
- 0: "wrt"
- 1: "wrf"
- 2: "er"
- 3: "ett"
- 4: "rftt"
Observed symbols and undischarged incoming inequalities
- e0 remaining
- f0 remaining
- r0 remaining
- t0 remaining
- w0 remaining
Distinct inferred inequalities — first-difference evidence
Empty.
Ready priority order — smallest at left; not heap storage
Empty.
Emitted alphabet prefix: "".
A newly ready smaller symbol competes immediately with existing entries. Counts retain pending inequalities until each release step. Isolated observed symbols still need emission. Final null in the exact state means Optional.empty(); final "" means Optional.of(""), a successful empty alphabet.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| words | ["wrt","wrf","er","ett","rftt"] |
| present | ["e","f","r","t","w"] |
| edges | [] |
| indegree | [{"symbol":"e","count":0},{"symbol":"f","count":0},{"symbol":"r","count":0},{"symbol":"t","count":0},{"symbol":"w","count":0}] |
| ready | [] |
| order | "" |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(String[] words) { 4 Objects.requireNonNull(words,"words");for(String word:words){Objects.requireNonNull(word,"word");for(int i=0;i<word.length();i++)if(word.charAt(i)<'a'||word.charAt(i)>'z')throw new IllegalArgumentException("expected lowercase ASCII");} 5 } 6 public static Optional<String> alienOrder(String[] words) { 7 validate(words);boolean[] present=new boolean[26];boolean[][] edge=new boolean[26][26];int[] indegree=new int[26];int count=0; 8 for(String word:words)for(int i=0;i<word.length();i++){int v=word.charAt(i)-'a';if(!present[v]){present[v]=true;count++;}} 9 for(int i=1;i<words.length;i++) { 10 String a=words[i-1],b=words[i];int p=0;while(p<Math.min(a.length(),b.length())&&a.charAt(p)==b.charAt(p))p++; 11 if(p==Math.min(a.length(),b.length())){if(a.length()>b.length())return Optional.empty();continue;} 12 int from=a.charAt(p)-'a',to=b.charAt(p)-'a';if(!edge[from][to]){edge[from][to]=true;indegree[to]++;} 13 } 14 PriorityQueue<Integer> ready=new PriorityQueue<>();for(int v=0;v<26;v++)if(present[v]&&indegree[v]==0)ready.add(v); 15 StringBuilder result=new StringBuilder(); 16 while(!ready.isEmpty()) { 17 int v=ready.remove();result.append((char)('a'+v)); 18 for(int next=0;next<26;next++)if(edge[v][next]&&--indegree[next]==0)ready.add(next); 19 } 20 return result.length()==count?Optional.of(result.toString()):Optional.empty(); 21 } 22 public static Optional<String> baseline(String[] words) { 23 validate(words);boolean[] present=new boolean[26];for(String word:words)for(int i=0;i<word.length();i++)present[word.charAt(i)-'a']=true; 24 int count=0;for(boolean value:present)if(value)count++;return enumerate(words,present,new boolean[26],new StringBuilder(),count); 25 } 26 private static Optional<String> enumerate(String[] words,boolean[] present,boolean[] used,StringBuilder order,int count) { 27 if(order.length()==count){int[] rank=new int[26];for(int i=0;i<count;i++)rank[order.charAt(i)-'a']=i;for(int i=1;i<words.length;i++){String a=words[i-1],b=words[i];int p=0;while(p<Math.min(a.length(),b.length())&&a.charAt(p)==b.charAt(p))p++;if(p==Math.min(a.length(),b.length())){if(a.length()>b.length())return Optional.empty();}else if(rank[a.charAt(p)-'a']>rank[b.charAt(p)-'a'])return Optional.empty();}return Optional.of(order.toString());} 28 for(int v=0;v<26;v++)if(present[v]&&!used[v]){used[v]=true;order.append((char)('a'+v));Optional<String> answer=enumerate(words,present,used,order,count);if(answer.isPresent())return answer;order.setLength(order.length()-1);used[v]=false;}return Optional.empty(); 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Register every observed symbol, including unconstrained letters.
Only observed lowercase-ASCII symbols belong in the answer. Validation scans the entire input before any semantic failure.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[]- indegree
[{"symbol":"e","count":0},{"symbol":"f","count":0},{"symbol":"r","count":0},{"symbol":"t","count":0},{"symbol":"w","count":0}]- ready
[]- order
""- phase
"initial"- current
null
- Use only the first differing position; deduplicate the implied edge.
Later positions do not constrain lexicographic comparison. A repeated observation is one inequality and contributes one indegree.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[{"from":"t","to":"f"}]- indegree
[{"symbol":"e","count":0},{"symbol":"f","count":1},{"symbol":"r","count":0},{"symbol":"t","count":0},{"symbol":"w","count":0}]- ready
[]- order
""- phase
"constraint"- current
null- comparison
{"left":0,"right":1,"index":2}- from
"t"- to
"f"- duplicate
false
- Use only the first differing position; deduplicate the implied edge.
Later positions do not constrain lexicographic comparison. A repeated observation is one inequality and contributes one indegree.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[{"from":"t","to":"f"},{"from":"w","to":"e"}]- indegree
[{"symbol":"e","count":1},{"symbol":"f","count":1},{"symbol":"r","count":0},{"symbol":"t","count":0},{"symbol":"w","count":0}]- ready
[]- order
""- phase
"constraint"- current
null- comparison
{"left":1,"right":2,"index":0}- from
"w"- to
"e"- duplicate
false
- Use only the first differing position; deduplicate the implied edge.
Later positions do not constrain lexicographic comparison. A repeated observation is one inequality and contributes one indegree.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[{"from":"t","to":"f"},{"from":"w","to":"e"},{"from":"r","to":"t"}]- indegree
[{"symbol":"e","count":1},{"symbol":"f","count":1},{"symbol":"r","count":0},{"symbol":"t","count":1},{"symbol":"w","count":0}]- ready
[]- order
""- phase
"constraint"- current
null- comparison
{"left":2,"right":3,"index":1}- from
"r"- to
"t"- duplicate
false
- Use only the first differing position; deduplicate the implied edge.
Later positions do not constrain lexicographic comparison. A repeated observation is one inequality and contributes one indegree.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[{"from":"t","to":"f"},{"from":"w","to":"e"},{"from":"r","to":"t"},{"from":"e","to":"r"}]- indegree
[{"symbol":"e","count":1},{"symbol":"f","count":1},{"symbol":"r","count":1},{"symbol":"t","count":1},{"symbol":"w","count":0}]- ready
[]- order
""- phase
"constraint"- current
null- comparison
{"left":3,"right":4,"index":0}- from
"e"- to
"r"- duplicate
false
- Seed the minimum-priority ready set.
Sorted chips show priority order, not the internal heap array. Choosing the least currently legal symbol gives the lexicographically smallest valid alphabet.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[{"from":"t","to":"f"},{"from":"w","to":"e"},{"from":"r","to":"t"},{"from":"e","to":"r"}]- indegree
[{"symbol":"e","count":1},{"symbol":"f","count":1},{"symbol":"r","count":1},{"symbol":"t","count":1},{"symbol":"w","count":0}]- ready
["w"]- order
""- phase
"seed"- current
null
- Emit the smallest currently unconstrained symbol.
Every emitted symbol has zero unmet incoming inequalities. Isolated symbols are included, not silently omitted.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[{"from":"t","to":"f"},{"from":"w","to":"e"},{"from":"r","to":"t"},{"from":"e","to":"r"}]- indegree
[{"symbol":"e","count":1},{"symbol":"f","count":1},{"symbol":"r","count":1},{"symbol":"t","count":1},{"symbol":"w","count":0}]- ready
[]- order
"w"- phase
"emit"- current
"w"
- Remove one outgoing inequality and admit any newly ready symbol.
Indegree counts inequalities not yet discharged, including pending edges of the current emitted symbol. Each distinct inequality is removed exactly once.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[{"from":"t","to":"f"},{"from":"w","to":"e"},{"from":"r","to":"t"},{"from":"e","to":"r"}]- indegree
[{"symbol":"e","count":0},{"symbol":"f","count":1},{"symbol":"r","count":1},{"symbol":"t","count":1},{"symbol":"w","count":0}]- ready
["e"]- order
"w"- phase
"release"- current
"w"- to
"e"
- Emit the smallest currently unconstrained symbol.
Every emitted symbol has zero unmet incoming inequalities. Isolated symbols are included, not silently omitted.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[{"from":"t","to":"f"},{"from":"w","to":"e"},{"from":"r","to":"t"},{"from":"e","to":"r"}]- indegree
[{"symbol":"e","count":0},{"symbol":"f","count":1},{"symbol":"r","count":1},{"symbol":"t","count":1},{"symbol":"w","count":0}]- ready
[]- order
"we"- phase
"emit"- current
"e"
- Remove one outgoing inequality and admit any newly ready symbol.
Indegree counts inequalities not yet discharged, including pending edges of the current emitted symbol. Each distinct inequality is removed exactly once.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[{"from":"t","to":"f"},{"from":"w","to":"e"},{"from":"r","to":"t"},{"from":"e","to":"r"}]- indegree
[{"symbol":"e","count":0},{"symbol":"f","count":1},{"symbol":"r","count":0},{"symbol":"t","count":1},{"symbol":"w","count":0}]- ready
["r"]- order
"we"- phase
"release"- current
"e"- to
"r"
- Emit the smallest currently unconstrained symbol.
Every emitted symbol has zero unmet incoming inequalities. Isolated symbols are included, not silently omitted.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[{"from":"t","to":"f"},{"from":"w","to":"e"},{"from":"r","to":"t"},{"from":"e","to":"r"}]- indegree
[{"symbol":"e","count":0},{"symbol":"f","count":1},{"symbol":"r","count":0},{"symbol":"t","count":1},{"symbol":"w","count":0}]- ready
[]- order
"wer"- phase
"emit"- current
"r"
- Remove one outgoing inequality and admit any newly ready symbol.
Indegree counts inequalities not yet discharged, including pending edges of the current emitted symbol. Each distinct inequality is removed exactly once.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[{"from":"t","to":"f"},{"from":"w","to":"e"},{"from":"r","to":"t"},{"from":"e","to":"r"}]- indegree
[{"symbol":"e","count":0},{"symbol":"f","count":1},{"symbol":"r","count":0},{"symbol":"t","count":0},{"symbol":"w","count":0}]- ready
["t"]- order
"wer"- phase
"release"- current
"r"- to
"t"
- Emit the smallest currently unconstrained symbol.
Every emitted symbol has zero unmet incoming inequalities. Isolated symbols are included, not silently omitted.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[{"from":"t","to":"f"},{"from":"w","to":"e"},{"from":"r","to":"t"},{"from":"e","to":"r"}]- indegree
[{"symbol":"e","count":0},{"symbol":"f","count":1},{"symbol":"r","count":0},{"symbol":"t","count":0},{"symbol":"w","count":0}]- ready
[]- order
"wert"- phase
"emit"- current
"t"
- Remove one outgoing inequality and admit any newly ready symbol.
Indegree counts inequalities not yet discharged, including pending edges of the current emitted symbol. Each distinct inequality is removed exactly once.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[{"from":"t","to":"f"},{"from":"w","to":"e"},{"from":"r","to":"t"},{"from":"e","to":"r"}]- indegree
[{"symbol":"e","count":0},{"symbol":"f","count":0},{"symbol":"r","count":0},{"symbol":"t","count":0},{"symbol":"w","count":0}]- ready
["f"]- order
"wert"- phase
"release"- current
"t"- to
"f"
- Emit the smallest currently unconstrained symbol.
Every emitted symbol has zero unmet incoming inequalities. Isolated symbols are included, not silently omitted.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[{"from":"t","to":"f"},{"from":"w","to":"e"},{"from":"r","to":"t"},{"from":"e","to":"r"}]- indegree
[{"symbol":"e","count":0},{"symbol":"f","count":0},{"symbol":"r","count":0},{"symbol":"t","count":0},{"symbol":"w","count":0}]- ready
[]- order
"wertf"- phase
"emit"- current
"f"
- All observed symbols form the smallest valid alphabet.
An empty alphabet is a successful empty String, distinct from Optional.empty for an impossible dictionary.
- words
["wrt","wrf","er","ett","rftt"]- present
["e","f","r","t","w"]- edges
[{"from":"t","to":"f"},{"from":"w","to":"e"},{"from":"r","to":"t"},{"from":"e","to":"r"}]- indegree
[{"symbol":"e","count":0},{"symbol":"f","count":0},{"symbol":"r","count":0},{"symbol":"t","count":0},{"symbol":"w","count":0}]- ready
[]- order
"wertf"- phase
"complete"- current
null
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
"wertf"
Deduplicate evidence and prioritize newly ready letters
Input: ["za","zb","ca","cb"] · Optional smallest alphabet: Optional.of("abzc")
Step 1 of 13: Register every observed symbol, including unconstrained letters.
Only observed lowercase-ASCII symbols belong in the answer. Validation scans the entire input before any semantic failure.
Phase: initial.
Input words — exact order; quotes preserve empty words
- 0: "za"
- 1: "zb"
- 2: "ca"
- 3: "cb"
Observed symbols and undischarged incoming inequalities
- a0 remaining
- b0 remaining
- c0 remaining
- z0 remaining
Distinct inferred inequalities — first-difference evidence
Empty.
Ready priority order — smallest at left; not heap storage
Empty.
Emitted alphabet prefix: "".
A newly ready smaller symbol competes immediately with existing entries. Counts retain pending inequalities until each release step. Isolated observed symbols still need emission. Final null in the exact state means Optional.empty(); final "" means Optional.of(""), a successful empty alphabet.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| words | ["za","zb","ca","cb"] |
| present | ["a","b","c","z"] |
| edges | [] |
| indegree | [{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0},{"symbol":"z","count":0}] |
| ready | [] |
| order | "" |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(String[] words) { 4 Objects.requireNonNull(words,"words");for(String word:words){Objects.requireNonNull(word,"word");for(int i=0;i<word.length();i++)if(word.charAt(i)<'a'||word.charAt(i)>'z')throw new IllegalArgumentException("expected lowercase ASCII");} 5 } 6 public static Optional<String> alienOrder(String[] words) { 7 validate(words);boolean[] present=new boolean[26];boolean[][] edge=new boolean[26][26];int[] indegree=new int[26];int count=0; 8 for(String word:words)for(int i=0;i<word.length();i++){int v=word.charAt(i)-'a';if(!present[v]){present[v]=true;count++;}} 9 for(int i=1;i<words.length;i++) { 10 String a=words[i-1],b=words[i];int p=0;while(p<Math.min(a.length(),b.length())&&a.charAt(p)==b.charAt(p))p++; 11 if(p==Math.min(a.length(),b.length())){if(a.length()>b.length())return Optional.empty();continue;} 12 int from=a.charAt(p)-'a',to=b.charAt(p)-'a';if(!edge[from][to]){edge[from][to]=true;indegree[to]++;} 13 } 14 PriorityQueue<Integer> ready=new PriorityQueue<>();for(int v=0;v<26;v++)if(present[v]&&indegree[v]==0)ready.add(v); 15 StringBuilder result=new StringBuilder(); 16 while(!ready.isEmpty()) { 17 int v=ready.remove();result.append((char)('a'+v)); 18 for(int next=0;next<26;next++)if(edge[v][next]&&--indegree[next]==0)ready.add(next); 19 } 20 return result.length()==count?Optional.of(result.toString()):Optional.empty(); 21 } 22 public static Optional<String> baseline(String[] words) { 23 validate(words);boolean[] present=new boolean[26];for(String word:words)for(int i=0;i<word.length();i++)present[word.charAt(i)-'a']=true; 24 int count=0;for(boolean value:present)if(value)count++;return enumerate(words,present,new boolean[26],new StringBuilder(),count); 25 } 26 private static Optional<String> enumerate(String[] words,boolean[] present,boolean[] used,StringBuilder order,int count) { 27 if(order.length()==count){int[] rank=new int[26];for(int i=0;i<count;i++)rank[order.charAt(i)-'a']=i;for(int i=1;i<words.length;i++){String a=words[i-1],b=words[i];int p=0;while(p<Math.min(a.length(),b.length())&&a.charAt(p)==b.charAt(p))p++;if(p==Math.min(a.length(),b.length())){if(a.length()>b.length())return Optional.empty();}else if(rank[a.charAt(p)-'a']>rank[b.charAt(p)-'a'])return Optional.empty();}return Optional.of(order.toString());} 28 for(int v=0;v<26;v++)if(present[v]&&!used[v]){used[v]=true;order.append((char)('a'+v));Optional<String> answer=enumerate(words,present,used,order,count);if(answer.isPresent())return answer;order.setLength(order.length()-1);used[v]=false;}return Optional.empty(); 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Register every observed symbol, including unconstrained letters.
Only observed lowercase-ASCII symbols belong in the answer. Validation scans the entire input before any semantic failure.
- words
["za","zb","ca","cb"]- present
["a","b","c","z"]- edges
[]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0},{"symbol":"z","count":0}]- ready
[]- order
""- phase
"initial"- current
null
- Use only the first differing position; deduplicate the implied edge.
Later positions do not constrain lexicographic comparison. A repeated observation is one inequality and contributes one indegree.
- words
["za","zb","ca","cb"]- present
["a","b","c","z"]- edges
[{"from":"a","to":"b"}]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":1},{"symbol":"c","count":0},{"symbol":"z","count":0}]- ready
[]- order
""- phase
"constraint"- current
null- comparison
{"left":0,"right":1,"index":1}- from
"a"- to
"b"- duplicate
false
- Use only the first differing position; deduplicate the implied edge.
Later positions do not constrain lexicographic comparison. A repeated observation is one inequality and contributes one indegree.
- words
["za","zb","ca","cb"]- present
["a","b","c","z"]- edges
[{"from":"a","to":"b"},{"from":"z","to":"c"}]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":1},{"symbol":"c","count":1},{"symbol":"z","count":0}]- ready
[]- order
""- phase
"constraint"- current
null- comparison
{"left":1,"right":2,"index":0}- from
"z"- to
"c"- duplicate
false
- Use only the first differing position; deduplicate the implied edge.
Later positions do not constrain lexicographic comparison. A repeated observation is one inequality and contributes one indegree.
- words
["za","zb","ca","cb"]- present
["a","b","c","z"]- edges
[{"from":"a","to":"b"},{"from":"z","to":"c"}]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":1},{"symbol":"c","count":1},{"symbol":"z","count":0}]- ready
[]- order
""- phase
"constraint"- current
null- comparison
{"left":2,"right":3,"index":1}- from
"a"- to
"b"- duplicate
true
- Seed the minimum-priority ready set.
Sorted chips show priority order, not the internal heap array. Choosing the least currently legal symbol gives the lexicographically smallest valid alphabet.
- words
["za","zb","ca","cb"]- present
["a","b","c","z"]- edges
[{"from":"a","to":"b"},{"from":"z","to":"c"}]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":1},{"symbol":"c","count":1},{"symbol":"z","count":0}]- ready
["a","z"]- order
""- phase
"seed"- current
null
- Emit the smallest currently unconstrained symbol.
Every emitted symbol has zero unmet incoming inequalities. Isolated symbols are included, not silently omitted.
- words
["za","zb","ca","cb"]- present
["a","b","c","z"]- edges
[{"from":"a","to":"b"},{"from":"z","to":"c"}]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":1},{"symbol":"c","count":1},{"symbol":"z","count":0}]- ready
["z"]- order
"a"- phase
"emit"- current
"a"
- Remove one outgoing inequality and admit any newly ready symbol.
Indegree counts inequalities not yet discharged, including pending edges of the current emitted symbol. Each distinct inequality is removed exactly once.
- words
["za","zb","ca","cb"]- present
["a","b","c","z"]- edges
[{"from":"a","to":"b"},{"from":"z","to":"c"}]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":1},{"symbol":"z","count":0}]- ready
["b","z"]- order
"a"- phase
"release"- current
"a"- to
"b"
- Emit the smallest currently unconstrained symbol.
Every emitted symbol has zero unmet incoming inequalities. Isolated symbols are included, not silently omitted.
- words
["za","zb","ca","cb"]- present
["a","b","c","z"]- edges
[{"from":"a","to":"b"},{"from":"z","to":"c"}]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":1},{"symbol":"z","count":0}]- ready
["z"]- order
"ab"- phase
"emit"- current
"b"
- Emit the smallest currently unconstrained symbol.
Every emitted symbol has zero unmet incoming inequalities. Isolated symbols are included, not silently omitted.
- words
["za","zb","ca","cb"]- present
["a","b","c","z"]- edges
[{"from":"a","to":"b"},{"from":"z","to":"c"}]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":1},{"symbol":"z","count":0}]- ready
[]- order
"abz"- phase
"emit"- current
"z"
- Remove one outgoing inequality and admit any newly ready symbol.
Indegree counts inequalities not yet discharged, including pending edges of the current emitted symbol. Each distinct inequality is removed exactly once.
- words
["za","zb","ca","cb"]- present
["a","b","c","z"]- edges
[{"from":"a","to":"b"},{"from":"z","to":"c"}]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0},{"symbol":"z","count":0}]- ready
["c"]- order
"abz"- phase
"release"- current
"z"- to
"c"
- Emit the smallest currently unconstrained symbol.
Every emitted symbol has zero unmet incoming inequalities. Isolated symbols are included, not silently omitted.
- words
["za","zb","ca","cb"]- present
["a","b","c","z"]- edges
[{"from":"a","to":"b"},{"from":"z","to":"c"}]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0},{"symbol":"z","count":0}]- ready
[]- order
"abzc"- phase
"emit"- current
"c"
- All observed symbols form the smallest valid alphabet.
An empty alphabet is a successful empty String, distinct from Optional.empty for an impossible dictionary.
- words
["za","zb","ca","cb"]- present
["a","b","c","z"]- edges
[{"from":"a","to":"b"},{"from":"z","to":"c"}]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0},{"symbol":"z","count":0}]- ready
[]- order
"abzc"- phase
"complete"- current
null
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
"abzc"
Repeated words still register isolated symbols
Input: ["cab","cab"] · Optional smallest alphabet: Optional.of("abc")
Step 1 of 8: Register every observed symbol, including unconstrained letters.
Only observed lowercase-ASCII symbols belong in the answer. Validation scans the entire input before any semantic failure.
Phase: initial.
Input words — exact order; quotes preserve empty words
- 0: "cab"
- 1: "cab"
Observed symbols and undischarged incoming inequalities
- a0 remaining
- b0 remaining
- c0 remaining
Distinct inferred inequalities — first-difference evidence
Empty.
Ready priority order — smallest at left; not heap storage
Empty.
Emitted alphabet prefix: "".
A newly ready smaller symbol competes immediately with existing entries. Counts retain pending inequalities until each release step. Isolated observed symbols still need emission. Final null in the exact state means Optional.empty(); final "" means Optional.of(""), a successful empty alphabet.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| words | ["cab","cab"] |
| present | ["a","b","c"] |
| edges | [] |
| indegree | [{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0}] |
| ready | [] |
| order | "" |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(String[] words) { 4 Objects.requireNonNull(words,"words");for(String word:words){Objects.requireNonNull(word,"word");for(int i=0;i<word.length();i++)if(word.charAt(i)<'a'||word.charAt(i)>'z')throw new IllegalArgumentException("expected lowercase ASCII");} 5 } 6 public static Optional<String> alienOrder(String[] words) { 7 validate(words);boolean[] present=new boolean[26];boolean[][] edge=new boolean[26][26];int[] indegree=new int[26];int count=0; 8 for(String word:words)for(int i=0;i<word.length();i++){int v=word.charAt(i)-'a';if(!present[v]){present[v]=true;count++;}} 9 for(int i=1;i<words.length;i++) { 10 String a=words[i-1],b=words[i];int p=0;while(p<Math.min(a.length(),b.length())&&a.charAt(p)==b.charAt(p))p++; 11 if(p==Math.min(a.length(),b.length())){if(a.length()>b.length())return Optional.empty();continue;} 12 int from=a.charAt(p)-'a',to=b.charAt(p)-'a';if(!edge[from][to]){edge[from][to]=true;indegree[to]++;} 13 } 14 PriorityQueue<Integer> ready=new PriorityQueue<>();for(int v=0;v<26;v++)if(present[v]&&indegree[v]==0)ready.add(v); 15 StringBuilder result=new StringBuilder(); 16 while(!ready.isEmpty()) { 17 int v=ready.remove();result.append((char)('a'+v)); 18 for(int next=0;next<26;next++)if(edge[v][next]&&--indegree[next]==0)ready.add(next); 19 } 20 return result.length()==count?Optional.of(result.toString()):Optional.empty(); 21 } 22 public static Optional<String> baseline(String[] words) { 23 validate(words);boolean[] present=new boolean[26];for(String word:words)for(int i=0;i<word.length();i++)present[word.charAt(i)-'a']=true; 24 int count=0;for(boolean value:present)if(value)count++;return enumerate(words,present,new boolean[26],new StringBuilder(),count); 25 } 26 private static Optional<String> enumerate(String[] words,boolean[] present,boolean[] used,StringBuilder order,int count) { 27 if(order.length()==count){int[] rank=new int[26];for(int i=0;i<count;i++)rank[order.charAt(i)-'a']=i;for(int i=1;i<words.length;i++){String a=words[i-1],b=words[i];int p=0;while(p<Math.min(a.length(),b.length())&&a.charAt(p)==b.charAt(p))p++;if(p==Math.min(a.length(),b.length())){if(a.length()>b.length())return Optional.empty();}else if(rank[a.charAt(p)-'a']>rank[b.charAt(p)-'a'])return Optional.empty();}return Optional.of(order.toString());} 28 for(int v=0;v<26;v++)if(present[v]&&!used[v]){used[v]=true;order.append((char)('a'+v));Optional<String> answer=enumerate(words,present,used,order,count);if(answer.isPresent())return answer;order.setLength(order.length()-1);used[v]=false;}return Optional.empty(); 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Register every observed symbol, including unconstrained letters.
Only observed lowercase-ASCII symbols belong in the answer. Validation scans the entire input before any semantic failure.
- words
["cab","cab"]- present
["a","b","c"]- edges
[]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0}]- ready
[]- order
""- phase
"initial"- current
null
- This equal/prefix pair imposes no symbol edge.
Equal words and shorter-before-longer prefixes need no character inequality.
- words
["cab","cab"]- present
["a","b","c"]- edges
[]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0}]- ready
[]- order
""- phase
"prefix-ok"- current
null- comparison
{"left":0,"right":1,"index":3}
- Seed the minimum-priority ready set.
Sorted chips show priority order, not the internal heap array. Choosing the least currently legal symbol gives the lexicographically smallest valid alphabet.
- words
["cab","cab"]- present
["a","b","c"]- edges
[]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0}]- ready
["a","b","c"]- order
""- phase
"seed"- current
null
- Emit the smallest currently unconstrained symbol.
Every emitted symbol has zero unmet incoming inequalities. Isolated symbols are included, not silently omitted.
- words
["cab","cab"]- present
["a","b","c"]- edges
[]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0}]- ready
["b","c"]- order
"a"- phase
"emit"- current
"a"
- Emit the smallest currently unconstrained symbol.
Every emitted symbol has zero unmet incoming inequalities. Isolated symbols are included, not silently omitted.
- words
["cab","cab"]- present
["a","b","c"]- edges
[]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0}]- ready
["c"]- order
"ab"- phase
"emit"- current
"b"
- Emit the smallest currently unconstrained symbol.
Every emitted symbol has zero unmet incoming inequalities. Isolated symbols are included, not silently omitted.
- words
["cab","cab"]- present
["a","b","c"]- edges
[]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0}]- ready
[]- order
"abc"- phase
"emit"- current
"c"
- All observed symbols form the smallest valid alphabet.
An empty alphabet is a successful empty String, distinct from Optional.empty for an impossible dictionary.
- words
["cab","cab"]- present
["a","b","c"]- edges
[]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0}]- ready
[]- order
"abc"- phase
"complete"- current
null
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
"abc"
A prefix conflict has no repair
Input: ["abc","ab"] · Optional smallest alphabet: Optional.empty()
Step 1 of 3: Register every observed symbol, including unconstrained letters.
Only observed lowercase-ASCII symbols belong in the answer. Validation scans the entire input before any semantic failure.
Phase: initial.
Input words — exact order; quotes preserve empty words
- 0: "abc"
- 1: "ab"
Observed symbols and undischarged incoming inequalities
- a0 remaining
- b0 remaining
- c0 remaining
Distinct inferred inequalities — first-difference evidence
Empty.
Ready priority order — smallest at left; not heap storage
Empty.
Emitted alphabet prefix: "".
A newly ready smaller symbol competes immediately with existing entries. Counts retain pending inequalities until each release step. Isolated observed symbols still need emission. Final null in the exact state means Optional.empty(); final "" means Optional.of(""), a successful empty alphabet.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| words | ["abc","ab"] |
| present | ["a","b","c"] |
| edges | [] |
| indegree | [{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0}] |
| ready | [] |
| order | "" |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(String[] words) { 4 Objects.requireNonNull(words,"words");for(String word:words){Objects.requireNonNull(word,"word");for(int i=0;i<word.length();i++)if(word.charAt(i)<'a'||word.charAt(i)>'z')throw new IllegalArgumentException("expected lowercase ASCII");} 5 } 6 public static Optional<String> alienOrder(String[] words) { 7 validate(words);boolean[] present=new boolean[26];boolean[][] edge=new boolean[26][26];int[] indegree=new int[26];int count=0; 8 for(String word:words)for(int i=0;i<word.length();i++){int v=word.charAt(i)-'a';if(!present[v]){present[v]=true;count++;}} 9 for(int i=1;i<words.length;i++) { 10 String a=words[i-1],b=words[i];int p=0;while(p<Math.min(a.length(),b.length())&&a.charAt(p)==b.charAt(p))p++; 11 if(p==Math.min(a.length(),b.length())){if(a.length()>b.length())return Optional.empty();continue;} 12 int from=a.charAt(p)-'a',to=b.charAt(p)-'a';if(!edge[from][to]){edge[from][to]=true;indegree[to]++;} 13 } 14 PriorityQueue<Integer> ready=new PriorityQueue<>();for(int v=0;v<26;v++)if(present[v]&&indegree[v]==0)ready.add(v); 15 StringBuilder result=new StringBuilder(); 16 while(!ready.isEmpty()) { 17 int v=ready.remove();result.append((char)('a'+v)); 18 for(int next=0;next<26;next++)if(edge[v][next]&&--indegree[next]==0)ready.add(next); 19 } 20 return result.length()==count?Optional.of(result.toString()):Optional.empty(); 21 } 22 public static Optional<String> baseline(String[] words) { 23 validate(words);boolean[] present=new boolean[26];for(String word:words)for(int i=0;i<word.length();i++)present[word.charAt(i)-'a']=true; 24 int count=0;for(boolean value:present)if(value)count++;return enumerate(words,present,new boolean[26],new StringBuilder(),count); 25 } 26 private static Optional<String> enumerate(String[] words,boolean[] present,boolean[] used,StringBuilder order,int count) { 27 if(order.length()==count){int[] rank=new int[26];for(int i=0;i<count;i++)rank[order.charAt(i)-'a']=i;for(int i=1;i<words.length;i++){String a=words[i-1],b=words[i];int p=0;while(p<Math.min(a.length(),b.length())&&a.charAt(p)==b.charAt(p))p++;if(p==Math.min(a.length(),b.length())){if(a.length()>b.length())return Optional.empty();}else if(rank[a.charAt(p)-'a']>rank[b.charAt(p)-'a'])return Optional.empty();}return Optional.of(order.toString());} 28 for(int v=0;v<26;v++)if(present[v]&&!used[v]){used[v]=true;order.append((char)('a'+v));Optional<String> answer=enumerate(words,present,used,order,count);if(answer.isPresent())return answer;order.setLength(order.length()-1);used[v]=false;}return Optional.empty(); 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Register every observed symbol, including unconstrained letters.
Only observed lowercase-ASCII symbols belong in the answer. Validation scans the entire input before any semantic failure.
- words
["abc","ab"]- present
["a","b","c"]- edges
[]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0}]- ready
[]- order
""- phase
"initial"- current
null
- A longer word precedes its own prefix: no alphabet can repair this.
Prefix length decides before any character order; this is a semantic impossibility, not a malformed-input exception.
- words
["abc","ab"]- present
["a","b","c"]- edges
[]- indegree
[{"symbol":"a","count":0},{"symbol":"b","count":0},{"symbol":"c","count":0}]- ready
[]- order
""- phase
"prefix-conflict"- current
null- comparison
{"left":0,"right":1,"index":2}
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
null
A two-letter cycle blocks the alphabet
Input: ["z","x","z"] · Optional smallest alphabet: Optional.empty()
Step 1 of 6: Register every observed symbol, including unconstrained letters.
Only observed lowercase-ASCII symbols belong in the answer. Validation scans the entire input before any semantic failure.
Phase: initial.
Input words — exact order; quotes preserve empty words
- 0: "z"
- 1: "x"
- 2: "z"
Observed symbols and undischarged incoming inequalities
- x0 remaining
- z0 remaining
Distinct inferred inequalities — first-difference evidence
Empty.
Ready priority order — smallest at left; not heap storage
Empty.
Emitted alphabet prefix: "".
A newly ready smaller symbol competes immediately with existing entries. Counts retain pending inequalities until each release step. Isolated observed symbols still need emission. Final null in the exact state means Optional.empty(); final "" means Optional.of(""), a successful empty alphabet.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| words | ["z","x","z"] |
| present | ["x","z"] |
| edges | [] |
| indegree | [{"symbol":"x","count":0},{"symbol":"z","count":0}] |
| ready | [] |
| order | "" |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(String[] words) { 4 Objects.requireNonNull(words,"words");for(String word:words){Objects.requireNonNull(word,"word");for(int i=0;i<word.length();i++)if(word.charAt(i)<'a'||word.charAt(i)>'z')throw new IllegalArgumentException("expected lowercase ASCII");} 5 } 6 public static Optional<String> alienOrder(String[] words) { 7 validate(words);boolean[] present=new boolean[26];boolean[][] edge=new boolean[26][26];int[] indegree=new int[26];int count=0; 8 for(String word:words)for(int i=0;i<word.length();i++){int v=word.charAt(i)-'a';if(!present[v]){present[v]=true;count++;}} 9 for(int i=1;i<words.length;i++) { 10 String a=words[i-1],b=words[i];int p=0;while(p<Math.min(a.length(),b.length())&&a.charAt(p)==b.charAt(p))p++; 11 if(p==Math.min(a.length(),b.length())){if(a.length()>b.length())return Optional.empty();continue;} 12 int from=a.charAt(p)-'a',to=b.charAt(p)-'a';if(!edge[from][to]){edge[from][to]=true;indegree[to]++;} 13 } 14 PriorityQueue<Integer> ready=new PriorityQueue<>();for(int v=0;v<26;v++)if(present[v]&&indegree[v]==0)ready.add(v); 15 StringBuilder result=new StringBuilder(); 16 while(!ready.isEmpty()) { 17 int v=ready.remove();result.append((char)('a'+v)); 18 for(int next=0;next<26;next++)if(edge[v][next]&&--indegree[next]==0)ready.add(next); 19 } 20 return result.length()==count?Optional.of(result.toString()):Optional.empty(); 21 } 22 public static Optional<String> baseline(String[] words) { 23 validate(words);boolean[] present=new boolean[26];for(String word:words)for(int i=0;i<word.length();i++)present[word.charAt(i)-'a']=true; 24 int count=0;for(boolean value:present)if(value)count++;return enumerate(words,present,new boolean[26],new StringBuilder(),count); 25 } 26 private static Optional<String> enumerate(String[] words,boolean[] present,boolean[] used,StringBuilder order,int count) { 27 if(order.length()==count){int[] rank=new int[26];for(int i=0;i<count;i++)rank[order.charAt(i)-'a']=i;for(int i=1;i<words.length;i++){String a=words[i-1],b=words[i];int p=0;while(p<Math.min(a.length(),b.length())&&a.charAt(p)==b.charAt(p))p++;if(p==Math.min(a.length(),b.length())){if(a.length()>b.length())return Optional.empty();}else if(rank[a.charAt(p)-'a']>rank[b.charAt(p)-'a'])return Optional.empty();}return Optional.of(order.toString());} 28 for(int v=0;v<26;v++)if(present[v]&&!used[v]){used[v]=true;order.append((char)('a'+v));Optional<String> answer=enumerate(words,present,used,order,count);if(answer.isPresent())return answer;order.setLength(order.length()-1);used[v]=false;}return Optional.empty(); 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Register every observed symbol, including unconstrained letters.
Only observed lowercase-ASCII symbols belong in the answer. Validation scans the entire input before any semantic failure.
- words
["z","x","z"]- present
["x","z"]- edges
[]- indegree
[{"symbol":"x","count":0},{"symbol":"z","count":0}]- ready
[]- order
""- phase
"initial"- current
null
- Use only the first differing position; deduplicate the implied edge.
Later positions do not constrain lexicographic comparison. A repeated observation is one inequality and contributes one indegree.
- words
["z","x","z"]- present
["x","z"]- edges
[{"from":"z","to":"x"}]- indegree
[{"symbol":"x","count":1},{"symbol":"z","count":0}]- ready
[]- order
""- phase
"constraint"- current
null- comparison
{"left":0,"right":1,"index":0}- from
"z"- to
"x"- duplicate
false
- Use only the first differing position; deduplicate the implied edge.
Later positions do not constrain lexicographic comparison. A repeated observation is one inequality and contributes one indegree.
- words
["z","x","z"]- present
["x","z"]- edges
[{"from":"z","to":"x"},{"from":"x","to":"z"}]- indegree
[{"symbol":"x","count":1},{"symbol":"z","count":1}]- ready
[]- order
""- phase
"constraint"- current
null- comparison
{"left":1,"right":2,"index":0}- from
"x"- to
"z"- duplicate
false
- Seed the minimum-priority ready set.
Sorted chips show priority order, not the internal heap array. Choosing the least currently legal symbol gives the lexicographically smallest valid alphabet.
- words
["z","x","z"]- present
["x","z"]- edges
[{"from":"z","to":"x"},{"from":"x","to":"z"}]- indegree
[{"symbol":"x","count":1},{"symbol":"z","count":1}]- ready
[]- order
""- phase
"seed"- current
null
- A residual cycle blocks a complete alphabet.
An empty alphabet is a successful empty String, distinct from Optional.empty for an impossible dictionary.
- words
["z","x","z"]- present
["x","z"]- edges
[{"from":"z","to":"x"},{"from":"x","to":"z"}]- indegree
[{"symbol":"x","count":1},{"symbol":"z","count":1}]- ready
[]- order
""- phase
"cycle"- current
null
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
null
Successful empty alphabet
Input: ["",""] · Optional smallest alphabet: Optional.of("")
Step 1 of 5: Register every observed symbol, including unconstrained letters.
Only observed lowercase-ASCII symbols belong in the answer. Validation scans the entire input before any semantic failure.
Phase: initial.
Input words — exact order; quotes preserve empty words
- 0: ""
- 1: ""
Observed symbols and undischarged incoming inequalities
Distinct inferred inequalities — first-difference evidence
Empty.
Ready priority order — smallest at left; not heap storage
Empty.
Emitted alphabet prefix: "".
A newly ready smaller symbol competes immediately with existing entries. Counts retain pending inequalities until each release step. Isolated observed symbols still need emission. Final null in the exact state means Optional.empty(); final "" means Optional.of(""), a successful empty alphabet.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| words | ["",""] |
| present | [] |
| edges | [] |
| indegree | [] |
| ready | [] |
| order | "" |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(String[] words) { 4 Objects.requireNonNull(words,"words");for(String word:words){Objects.requireNonNull(word,"word");for(int i=0;i<word.length();i++)if(word.charAt(i)<'a'||word.charAt(i)>'z')throw new IllegalArgumentException("expected lowercase ASCII");} 5 } 6 public static Optional<String> alienOrder(String[] words) { 7 validate(words);boolean[] present=new boolean[26];boolean[][] edge=new boolean[26][26];int[] indegree=new int[26];int count=0; 8 for(String word:words)for(int i=0;i<word.length();i++){int v=word.charAt(i)-'a';if(!present[v]){present[v]=true;count++;}} 9 for(int i=1;i<words.length;i++) { 10 String a=words[i-1],b=words[i];int p=0;while(p<Math.min(a.length(),b.length())&&a.charAt(p)==b.charAt(p))p++; 11 if(p==Math.min(a.length(),b.length())){if(a.length()>b.length())return Optional.empty();continue;} 12 int from=a.charAt(p)-'a',to=b.charAt(p)-'a';if(!edge[from][to]){edge[from][to]=true;indegree[to]++;} 13 } 14 PriorityQueue<Integer> ready=new PriorityQueue<>();for(int v=0;v<26;v++)if(present[v]&&indegree[v]==0)ready.add(v); 15 StringBuilder result=new StringBuilder(); 16 while(!ready.isEmpty()) { 17 int v=ready.remove();result.append((char)('a'+v)); 18 for(int next=0;next<26;next++)if(edge[v][next]&&--indegree[next]==0)ready.add(next); 19 } 20 return result.length()==count?Optional.of(result.toString()):Optional.empty(); 21 } 22 public static Optional<String> baseline(String[] words) { 23 validate(words);boolean[] present=new boolean[26];for(String word:words)for(int i=0;i<word.length();i++)present[word.charAt(i)-'a']=true; 24 int count=0;for(boolean value:present)if(value)count++;return enumerate(words,present,new boolean[26],new StringBuilder(),count); 25 } 26 private static Optional<String> enumerate(String[] words,boolean[] present,boolean[] used,StringBuilder order,int count) { 27 if(order.length()==count){int[] rank=new int[26];for(int i=0;i<count;i++)rank[order.charAt(i)-'a']=i;for(int i=1;i<words.length;i++){String a=words[i-1],b=words[i];int p=0;while(p<Math.min(a.length(),b.length())&&a.charAt(p)==b.charAt(p))p++;if(p==Math.min(a.length(),b.length())){if(a.length()>b.length())return Optional.empty();}else if(rank[a.charAt(p)-'a']>rank[b.charAt(p)-'a'])return Optional.empty();}return Optional.of(order.toString());} 28 for(int v=0;v<26;v++)if(present[v]&&!used[v]){used[v]=true;order.append((char)('a'+v));Optional<String> answer=enumerate(words,present,used,order,count);if(answer.isPresent())return answer;order.setLength(order.length()-1);used[v]=false;}return Optional.empty(); 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Register every observed symbol, including unconstrained letters.
Only observed lowercase-ASCII symbols belong in the answer. Validation scans the entire input before any semantic failure.
- words
["",""]- present
[]- edges
[]- indegree
[]- ready
[]- order
""- phase
"initial"- current
null
- This equal/prefix pair imposes no symbol edge.
Equal words and shorter-before-longer prefixes need no character inequality.
- words
["",""]- present
[]- edges
[]- indegree
[]- ready
[]- order
""- phase
"prefix-ok"- current
null- comparison
{"left":0,"right":1,"index":0}
- Seed the minimum-priority ready set.
Sorted chips show priority order, not the internal heap array. Choosing the least currently legal symbol gives the lexicographically smallest valid alphabet.
- words
["",""]- present
[]- edges
[]- indegree
[]- ready
[]- order
""- phase
"seed"- current
null
- All observed symbols form the smallest valid alphabet.
An empty alphabet is a successful empty String, distinct from Optional.empty for an impossible dictionary.
- words
["",""]- present
[]- edges
[]- indegree
[]- ready
[]- order
""- phase
"complete"- current
null
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
""
Test the contract
Input:
Only repeated empty words
Output:Optional.of("")Successful empty alphabet.
Input:
Repeated words and isolated letters
Output:all observed letters once, smallest valid orderNo inequality is inferred from equality.
Input:
Longer word before prefix, or a cycle
Output:Optional.empty()Two different semantic obstructions.
Input:
Invalid character after an earlier prefix conflict
Output:IllegalArgumentExceptionFull validation precedes early failure.
Input:
All 26 letters in one long word
Output:abcdefghijklmnopqrstuvwxyzMain path includes isolated symbols without factorial search.
Common mistakes and counterexamples
Use every differing position
Counterexample: In [ab,ba], the first position requires a<b; adding b<a from the second creates a false cycle.
Stop at the first mismatch.
Ignore invalid prefix order
Counterexample: [abc,ab] has no first mismatch and cannot be accepted.
Compare lengths after the common prefix.
Count a repeated inequality twice but store one edge
Counterexample: [za,zb,ca,cb] observes a<b twice.
Increment degree only when setting a previously absent edge.
Forget isolated symbols or use FIFO for the smallest answer
Counterexample: A single word cab still requires output abc; newly ready b must beat queued z in the example.
Register all symbols and use a min-priority queue.
Follow-ups
Return any valid alphabet instead.
A FIFO ready queue suffices for existence plus one order. State that its output need not be smallest and accept all rank-valid permutations.
Support a larger Unicode alphabet.
Choose code points or graphemes explicitly, coordinate-compress symbols, and replace fixed arrays with suitable maps/sets. Define the tie-break comparator and count key-comparison/storage costs.
Determine whether the inferred alphabet is unique.
In an acyclic graph, more than one available source at any step yields multiple valid orders. Distinguish ambiguity from impossibility, and account for observed isolated symbols.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 182/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.