Найдите лексикографически наименьшую строку, выполнив данные операции N раз

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

• Удалите 1- й символ S и вставьте его в стек X .
• Удалите вершину стека X и добавьте ее в конец другой строки Y, которая изначально пуста.

Пример:

Input: S = “cab”
Output: abc
Explanation: The given string can be obtained using the following operations:

1. Perform operation 1. Hence, S = “ab”, X = “c”, Y = “”.
2. Perform operation 1. Hence, S = “b”, X = “ca”, Y = “”.
3. Perform operation 2. Hence, S = “b”, X = “c”, Y = “a”.
4. Perform operation 1. Hence, S = “”, X = “cb”, Y = “a”.
5. Perform operation 2. Hence, S = “”, X = “c”, Y = “ab”.
6. Perform operation 2. Hence, S = “”, X = “”, Y = “abc”.

Now, each of the given operations is performed N times and the string obtained is “abc” which is the smallest possible.

Input: S = “acdb”
Output: abdc

Подход: Данную задачу можно решить с помощью жадного подхода. Идея состоит в том, чтобы выполнить 1 ^-й операция до тех пор, пока вершина стека не будет содержать наименьший символ, после чего он может быть добавлен к строке Y . Это можно эффективно сделать, поддерживая массив суффиксов, где suff[i] хранит наименьшее значение ASCII суффикса до i ^-го символа. Ниже приведены шаги, которые необходимо выполнить:

• Перейдите строку и создайте массив суффиксов suff[] по мере необходимости.
• Если стек X не пуст, а suff[i] больше, чем равен верхнему символу стека X , извлечь верхний символ стека X и добавить его в строку Y .
• Else Если suff[i] равно S[i] добавить в строку Y .
• В противном случае поместите символ S[i] в стек X .

Ниже приведена реализация вышеуказанного подхода:

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