Out of the 200 or so people I interviewed where I posed this question, only one went with Multimap.

You’re hired. :)

Kidding aside, going with a map of string lists as a first iteration of a solution for this is perfectly fine. The followup is to optimized the algo for space and time, and there are intuitive steps if you implement it as a map of lists.