Algorithm · Amazon · Medium
Developers at Amazon are building a text-generation utility for a new product. At present the utility is only capable of producing "special strings," meaning strings in which no two neighboring characters are identical. You are given a string s consisting of n characters. Produce a special string of the same length n that comes after s in lexicographic order. When more than one special string satisfies this, choose the one that is lexicographically smallest. Definitions you…