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

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

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

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

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.