198. Alien Dictionary

Compare adjacent words to extract character ordering constraints, then topological sort.

Approach

1. Compare each pair of adjacent words to find the first differing character — this gives a directed edge.
2. Build a graph and topological sort (BFS).
3. If cycle detected or not all chars included, return empty string.

Complexity

• Time: O(C) where C = total characters
• Space: O(1) since alphabet is fixed size

import java.util.*;

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<>();
        Map<Character, Integer> inDeg = new HashMap<>();

        for (String w : words) {
            for (char c : w.toCharArray()) {
                adj.putIfAbsent(c, new HashSet<>());
                inDeg.putIfAbsent(c, 0);
            }
        }

        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i], w2 = words[i + 1];
            int minLen = Math.min(w1.length(), w2.length());
            if (w1.length() > w2.length() && w1.substring(0, minLen).equals(w2.substring(0, minLen))) {
                return "";
            }
            for (int j = 0; j < minLen; j++) {
                if (w1.charAt(j) != w2.charAt(j)) {
                    if (!adj.get(w1.charAt(j)).contains(w2.charAt(j))) {
                        adj.get(w1.charAt(j)).add(w2.charAt(j));
                        inDeg.put(w2.charAt(j), inDeg.get(w2.charAt(j)) + 1);
                    }
                    break;
                }
            }
        }

        Queue<Character> queue = new LinkedList<>();
        for (Map.Entry<Character, Integer> entry : inDeg.entrySet()) {
            if (entry.getValue() == 0) {
                queue.add(entry.getKey());
            }
        }

        StringBuilder result = new StringBuilder();
        while (!queue.isEmpty()) {
            char c = queue.poll();
            result.append(c);
            for (char nb : adj.get(c)) {
                inDeg.put(nb, inDeg.get(nb) - 1);
                if (inDeg.get(nb) == 0) {
                    queue.add(nb);
                }
            }
        }

        return result.length() == inDeg.size() ? result.toString() : "";
    }
}