Лексикографически наименьшая строка, не являющаяся подпоследовательностью заданной строки

Для заданной строки S задача состоит в том, чтобы найти лексикографически наименьшую строку, а не подпоследовательность заданной строки S.

Примеры:

Input: S = “abcdefghijklmnopqrstuvwxyz”
Output: 
aa
Explanation:
String “aa” is the lexicographically smallest string which is not present in the given string as a subsequence.

Input: S = “aaaa”
Output: 
aaab
Explanation:
String “aaa” is the lexicographically smallest string which is not present in the given string as a subsequence.

Подход: Идея состоит в том, чтобы решить данную проблему, чтобы найти частоту символа «а» в заданной строке (скажем, f ). Если значение f меньше длины строки, то ответом будет строка, образованная конкатенацией 'a' f+1 раз, поскольку aaa….(f+1 раз) будет требуемой лексикографически наименьшей строкой что не является подпоследовательностью. В противном случае ответом будет строка, образованная конкатенацией ' a' (f-1 раз) и 'b' в конце строки.

Временная сложность: O(N)
Вспомогательное пространство: O(1)