Some cities are going to be renamed and accordingly name of their railway stations will also change. Changing the name of railway station should also result in changed station code. Railways have an idea that station code should be the shortest prefix out of all railway stations renamed prior to this. If some city has same name, then prefix will be the name with suffix as the count of occurence of that city prior to this and including this, seperated with spaces.
Given N renamed cities consisting of lowercase alphabets only. The task is to generate a station ID for all the stations.
Cities[] = {shimla,safari,jammu,delhi, jammu,dehradun} Output: s sa j d jammu 2 deh