Letter Permissions Down a DAG
A DAG has n nodes, 0 to n - 1, and directed [parent, child] edges. Each node has an allow string and a disallow string of capital letters A–Z. Permissions flow downward:
- A source (no parents) inherits nothing.
- Any other node inherits a letter only if every parent's final state allows it.
- A node's final state is its inherited letters plus its own
allow, minus its owndisallow.
Return each node's final allowed letters as a string in alphabetical order, or "-" when it allows nothing.
finalAllowed(3, [[0, 1], [1, 2]], ["A", "", "C"], ["", "B", ""]) -> ["A", "A", "AC"] finalAllowed(3, [[0, 2], [1, 2]], ["AB", "A", ""], ["", "", ""]) -> ["AB", "A", "A"]
Hints
Hint 1
Represent a letter set as a 26-bit mask; union, intersection and difference become OR, AND and AND NOT.
Hint 2
Process nodes in topological order so every parent's final mask exists before a child needs it. Start each non-source at the all-ones mask and AND each parent's final into it.