Propagate Permission Letters Through a DAG Using Each Node's Final State

A permission system is modeled as a directed acyclic graph with `n` nodes, numbered `0` to `n - 1`. Permissions are single lowercase letters. An edge `[u, v]` means `u` is a parent of `v`, and `v` inherits from `u`. Each node `i` also has its own rules: a string `allow[i]` of letters it grants, and a string `disallow[i]` of letters it revokes. The final state of a node is the set of letters it ends up with. To compute it, take the union of the final states of all the node's parents (the empty set if it has no parents), add every letter in `allow[i]`, then remove every letter in `disallow[i]`. A node passes only its final state down to its children. Its `allow` and `disallow` rules are not passed down separately, so a letter that one node removes can be granted again further down the graph. Return the final state of every node. ### Function Signature ```python def final_letters(n: int, edges: list[list[int]], allow: list[str], disallow: list[str]) -> list[str]: ``` ### Rules - `final(i)` is the union of `final(p)` over every parent `p` of `i`, together with the letters of `allow[i]`, minus the letters of `disallow[i]`. - A node with no parents starts from the empty set, so its final state is exactly the letters of `allow[i]`. - A letter in `disallow[u]` is missing from `final(u)`, so it is not inherited through `u`. A child of `u` can still get it from another parent or from its own `allow`. - Node numbers do not follow topological order: a parent can have a larger number than its child. - Return a list of `n` strings in which element `i` is `final(i)`, written as its letters in ascending alphabetical order with no repeats. A node whose final state is empty maps to `""`. ### Constraints - `1 <= n <= 100000` - `0 <= len(edges) <= 200000` - Every edge is `[u, v]` with `0 <= u <= n - 1`, `0 <= v <= n - 1` and `u != v`. No edge appears twice. - The graph contains no directed cycle. - `len(allow) == len(disallow) == n` - Each `allow[i]` and each `disallow[i]` is a string of 0 to 26 distinct lowercase English letters (`a` to `z`), in any order. - For every node `i`, `allow[i]` and `disallow[i]` have no letter in common. ### Examples **Example 1** ```text Input: n = 4 edges = [[0, 1], [0, 2], [1, 3], [2, 3]] allow = ["ab", "c", "", "d"] disallow = ["", "a", "b", ""] Output: ["ab", "bc", "a", "abcd"] ``` Node 0 has no parents, so it holds `a` and `b`. Node 1 inherits `{a, b}`, adds `c` and removes `a`, giving `"bc"`. Node 2 inherits `{a, b}` and removes `b`, giving `"a"`. Node 3 has two parents, so it receives `b` and `c` from node 1 and `a` from node 2, then adds `d`. **Example 2** ```text Input: n = 3 edges = [[0, 1], [1, 2]] allow = ["xy", "", "x"] disallow = ["", "xy", ""] Output: ["xy", "", "x"] ``` Node 1 removes both letters, so it passes the empty set to node 2. Node 2 grants `x` again through its own `allow`. **Example 3** ```text Input: n = 3 edges = [[2, 0], [1, 0]] allow = ["m", "qp", "r"] disallow = ["q", "", ""] Output: ["mpr", "pq", "r"] ``` Nodes 1 and 2 have no parents, so their final states are their own `allow` letters, written in sorted order. Node 0 inherits `p`, `q` and `r`, adds `m`, and removes `q`.