Surely the algorithm would iterate over the RHS and use the O(1) lookup in the LHS dict? Copy all then remove for -.
-