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.

Final Permission Letters in an Inheritance DAG

Hints

1. A node's final state is fully determined by its parents' final states plus its own allow and disallow strings; the rule strings themselves never travel down an edge.
2. Node numbers are not a safe processing order: a parent can have a larger number than its child, and a node with several parents needs all of their final states first.
3. There are only 26 possible letters, so every state is a small set; remember each output string lists its letters in ascending order.

Approach

Represent each set of letters as a 26-bit mask (bit 0 = 'a'). Build child lists and in-degrees from the edges, then run Kahn's topological sort: start a queue with every node that has no parent. When node u is dequeued, compute final(u) = (inherited(u) | mask(allow[u])) & ~mask(disallow[u]), then OR final(u) into inherited(v) for every child v, decrement v's in-degree, and enqueue v when it reaches zero. Invariant: a node is dequeued only after every one of its parents has been dequeued, so at that moment inherited(u) is exactly the union of all its parents' final states, and the recurrence is evaluated exactly as defined. Because the graph is acyclic, every node's in-degree eventually reaches zero, so each node is finalized exactly once, independent of node numbering or edge order. Each mask is then written out by scanning bits 0..25, which yields the letters in ascending order with no repeats. Edge cases: n = 1 or no edges (every node is a root, so its state is its sorted allow letters), empty allow/disallow strings (empty state maps to ''), disallowing a letter the node never had (no effect), revoking all 26 letters (the node passes the empty set, and a descendant may re-grant letters), letters arriving from several parents (union, so no duplicates), and long chains in any numbering, which the iterative queue handles without recursion-depth limits.

• Time complexity: O(n + m), where m = len(edges); each node does O(26) work for its rule strings and output
• Space complexity: O(n + m)