Выведите наибольшее целое число, образованное вставкой цифры X в заданную строку

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

Примеры:

Input: S = “99”, X = 9
Output: 999
Explanation: 
The largest number that can be formed is 999 after inserting 9 into “99”.

Input: S = “-13”, X = 2
Output: -123
Explanation: 
The largest number that can be formed is -123 after inserting 2 into “-13”.

Подход: проблема может быть решена путем повторения символа строки S . Выполните следующие шаги, чтобы решить эту проблему:

• Если число S положительное, то выполните следующие действия:
  • Выполните итерацию в диапазоне [0, N-1], используя переменную i , и выполните следующие шаги :
    • Если S[i] меньше X , то вставьте цифру X перед S[i] и разорвите цикл .
  • Если ни один из вышеперечисленных случаев не удовлетворяет, добавьте цифру X в конец строки S.
• В противном случае, если число S отрицательное, выполните следующие действия:
  • Повторите в диапазоне [0, N-1] использование переменной i и выполните следующие шаги:
    • Если S[i] меньше X , то вставьте цифру X перед S[i] и разорвите цикл.
  • Если ни один из вышеперечисленных случаев не удовлетворяет, добавьте цифру X в конец строки S.
• Наконец, выведите максимально возможную строку, представленную S .

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

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