Comma Sprinkler

This problem asks us to add commas to an input string with the rules that if a given word is is pre or succeeded with a comma, then every instance of that word should be as well.

Iteratively applying the rules will likely be too slow. We can see, though, that when we add a comma after a word, we have to look at all the next words and add a comma BEFORE all of them, and then a comma AFTER all the words that precede those words...etc. This sounds a lot like a BFS, which it turns out is the solution.

Preprocess the string into a graph where you have nodes two nodes for each word, a "comma before" version of the node, and a "comma after." We add edges for each other word we have to add a comma for if we add it to a given node. So if we reach the "comma before" node for a word, it means we have to add a comma before all instance of that word, and thus we have to draw edges to the "comma after" node for each word that precede that word in the text. We then BFS through the graph starting where any commas existed in the input string, remembering which nodes we traversed.

After this, we can trivially create the output string in one pass, between each word checking if we need a comma after the trailing word, or before the next word (note: this should always be either neither or both!), and adding it.

Since the number of words and edges is on the order of hundreds of thousands, this should be plenty fast.