Longest Chain of Linked Names in a Directed Acyclic Graph
Company: Oscar
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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
```python
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.
Overview: A graph coding question: given directed pairs of names that together form an acyclic graph, return the number of names in the longest chain that follows the pairs in order. It tests building an adjacency structure from string pairs and computing the longest path in a directed acyclic graph efficiently on large inputs.
You are given a list of name pairs. Each pair `[u, v]` says that the name `v` may come directly after the name `u`. 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 number of names in the longest chain.
Implement `longest_name_chain(pairs)`, which returns an integer.
**Rules**
- Direction matters: the pair `[u, v]` allows `u` followed by `v`, never `v` followed by `u`.
- The length of a chain is the number of names in it, not the number of links, so 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.
**Example 1**
- Input: `pairs = [["a", "b"], ["b", "c"], ["d", "e"]]`
- Output: `3`
- Explanation: The chain `a -> b -> c` has three names. Every other chain, such as `d -> e`, is 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 go from `ben` back to `amy` or `cal`, because direction matters.
**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`, so it fits in a 32-bit signed integer.
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 (fits in a 32-bit signed integer)
Examples
Input: ([['a', 'b'], ['b', 'c'], ['d', 'e']],)
Expected Output: 3
Input: ([['w', 'x'], ['x', 'y'], ['y', 'z'], ['x', 'z']],)
Expected Output: 4
Hints
- Treat every name as a node and every pair [u, v] as a directed edge u -> v. Which classic graph quantity is the answer?
- 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.
- 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.