We have a dictionary of words dict, and we are writing words down in a single line using the following rules. The first written word can be any word from dict. Each subsequent written word must start with the same letter as the last letter of the previous written word, and that shared letter is only written once (see examples). Only words from dict can be used, but each word can be used an unlimited number of times.
Using the rules above, construct the lexicographically earliest line with length greater than or equal to len characters. Return an empty String ("") if such a line cannot be constructed.