Longest Chain of Linked Names in a Directed Acyclic Graph

You are given a list of name pairs. Each pair [u, v] means that the name v may directly follow the name u in a chain. A chain is a sequence of names in which every two consecutive names x, y appear, in that order, as a pair [x, y] in the input. The pairs never form a cycle.

Return the length of the longest chain, measured as the number of names it contains.

Function Signature

def longest_name_chain(pairs: list[list[str]]) -> int:

Rules

• Direction matters: the pair [u, v] allows u followed by v, never v followed by u.
• Length counts names, not links: a chain made of a single pair has length 2.
• A name may appear in any number of pairs, in either position.
• Only the length is returned, not the chain itself, so the answer is unique even when several chains share the maximum length.

Constraints

• 1 <= len(pairs) <= 100000
• Each pairs[i] contains exactly two names u and v, with u != v.
• Each name is a non-empty string of at most 20 lowercase English letters.
• No pair appears more than once.
• The directed graph with an edge from u to v for every pair [u, v] contains no directed cycle.
• The result is an integer from 2 to the number of distinct names, which is at most 200000.

Examples

Example 1

• Input: pairs = [["a", "b"], ["b", "c"], ["d", "e"]]
• Output: 3
• Explanation: The chain a -> b -> c has three names. The only other chains, such as d -> e, are shorter.

Example 2

• Input: pairs = [["w", "x"], ["x", "y"], ["y", "z"], ["x", "z"]]
• Output: 4
• Explanation: w -> x -> y -> z has four names. The direct pair ["x", "z"] only gives the shorter chain w -> x -> z.

Example 3

• Input: pairs = [["amy", "ben"], ["cal", "ben"], ["ben", "dan"]]
• Output: 3
• Explanation: Both amy -> ben -> dan and cal -> ben -> dan have three names. No chain can continue from ben back to amy or cal, because direction matters.

Longest Directed Name Chain

Hints

1. Treat every name as a node and every pair [u, v] as a directed edge u -> v. Which classic graph quantity is the answer?
2. Because the graph has no cycles, the names can be put in an order where each name comes after every name that may precede it in a chain.
3. For each name, track the length of the longest chain that ends at it, and push that value forward along its outgoing pairs. A chain can contain over 100000 names, so avoid deep recursion.

Approach

Map each distinct name to an integer id and build the directed graph with one edge u -> v per pair, counting each name's in-degree. The answer is the longest path in this acyclic graph, measured in nodes. Let best[x] be the number of names in the longest chain that ends at x; it starts at 1 for every name (the chain made of x alone). Kahn's algorithm processes names in topological order: a queue holds names whose in-degree has dropped to zero, which means every name that can precede them has already been processed, so their best value is final. When x is taken from the queue, each successor y gets best[y] = max(best[y], best[x] + 1) and loses one in-degree; y joins the queue once its in-degree reaches zero. The largest best value seen is the length of the longest chain. Because every pair is a real edge, the answer is at least 2. The loop is iterative, so a chain of 100000+ names does not overflow the call stack, and ties between equally long chains do not matter because only the length is returned.

• Time complexity: O(P) with P = len(pairs) (each name has at most 20 letters, so hashing a name is O(1))
• Space complexity: O(P)