Разделить заданную числовую строку не более чем на две возрастающие подпоследовательности, которые образуют возрастающую строку при конкатенации.

Дана строка S , состоящая из N цифр, задача состоит в том, чтобы разбить строку не более чем на две возрастающие подпоследовательности так, чтобы их конкатенация также образовывала возрастающую строку. Если это невозможно сделать, то выведите «-1» .

Примеры:

Input: S = “040425524644”
Output: 0022444 44556
Explanation:
One of the possible way to partition the given string S is {“0022444”, “44556”}. Both are in increasing order and the concatenation of them are also increasing “0022444” + ‘”4556″ = “002244444556”.
Therefore, print both the subsequence formed.

Input: S = “123456789”
Output: 123456789

Наивный подход: самый простой подход к решению проблемы — сгенерировать все возможные подпоследовательности и проверить, удовлетворяют ли любые две непересекающиеся подпоследовательности заданному условию. Если найдено, что это правда , то выведите обе подпоследовательности.

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

Эффективный подход: описанный выше подход можно оптимизировать, поместив все значения меньше X в первую подпоследовательность и все элементы больше X во вторую подпоследовательность, а все элементы, равные X , определяются на основе их положения для всех X. в диапазоне [0, 9] . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, pos для хранения позиции, где меньше pos в первой подпоследовательности, больше pos во второй подпоследовательности, а элемент, равный pos , будет в подпоследовательности на основе их позиции.
• Инициализируйте массив res[] , в котором будет храниться, какой элемент принадлежит какой подпоследовательности.
• Итерируйте позицию в диапазоне [0, 9] и выполните следующие шаги:
  1. Инициализируйте две переменные last1 как 0 и last2 как pos , которые хранят последние элементы, которые были помещены в подпоследовательности 1 и 2 соответственно.
  2. Инициализируйте флаг логической переменной как 1 , который хранит, является ли обработанная подпоследовательность допустимой или нет.
  3. Выполните итерацию в диапазоне [0, N-1], используя i в качестве переменной, и выполните следующие шаги:
     • Если last2 ≤ S[i] , измените значение last2 как S[i] и res[i] как 2 .
     • В противном случае, если last1 ≤ S[i] , измените значение last1 на S[i] и res[i] на 1 .
     • В противном случае измените значение флага на 0 .
  4. Проверьте, больше ли значение last чем pos , затем измените значение flag на 0 .
  5. Если значение флага равно 1 , то выведите массив res в качестве ответа и прервите цикл.
• После выполнения вышеуказанных шагов выведите -1 , если не найдено ни одной возможной подпоследовательности.

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

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