Максимизируйте число, образованное заменой соседних цифр их суммой

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

Примеры:

Input: 10057 
Output: 10012 
Explanation: 10012 is the maximum number that we can form since 5+7=12. 

Input: 30 
Output: 3 .
Explanation: 3+0=3 the only option .

Подход: Задача может быть решена на основе следующего наблюдения:

Может быть два случая:

If there is at least one pair having sum greater than or equal to 10:

•  The sum of the numbers will always be less than the number formed by the two adjacent digits but the number of digits will be same.
• So find such a pair that is at the right end of the number and replace the rightmost such pair.

If there is no such pair:

• Then the newly formed number will always have on less digit than N.
• To maximize the number it is optimal to replace the leftmost such pair because the sum will always be greater than any of the digits.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Прежде всего, мы преобразуем данное число в строку для удобства. Пусть строка будет s .
• Предположим, что есть пара, сумма которых больше 10:
  • Траверс со спины.
  • Если такая пара найдена, замените их суммой этих цифр.
• В противном случае такой пары нет.
  • Замените крайнюю левую пару.
  • Крайняя левая пара образована первыми двумя цифрами. Поэтому замените их их суммой.
• Образованное число является искомым ответом.

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

Временная сложность: O(M), где M — количество цифр в числе.
Вспомогательное пространство: O(M)