# Algorithm for smallest String without a given prefix

How can I find the lexicographicaly smallest string that doesn't start with a given prefix AND is lexicographicaly bigger than the given prefix? Example:

1. prefix : cat; next string : cau

2. prefix : cazz next string; cb

• If your alphabet has $n$ characters, transform the word to $n$-base number, add 1, transfer back – Eugene Mar 27 '17 at 3:14
• I don't understand your question. The lexicographically smallest string that doesn't start with a given non-empty prefix is the empty string. After that comes the string a. And so on. Perhaps you would like to revise your question? – Yuval Filmus Mar 27 '17 at 6:44
• @Yuvas Filmus I edited my question – SoloNasus Mar 27 '17 at 16:03

## 1 Answer

There is no solution if all characters in the input string are equal to the last character in the alphabet (this includes the case of the empty string).

Otherwise, as long as the last character in the input string is the last character in the alphabet, remove it from the string. Then replace the last character of the result with the next character in the alphabet.