Lexicographically Smallest String with Increment Operations

You are given a string consisting only of digits (0–9). You may perform the following operation as many times as you wish: Pick any one digit from the string and remove it. Increment that digit by 1 (unless it is already 9—in that case it remains 9). Insert the resulting digit at any position in the string. Your goal is to produce the lexicographically smallest string possible by applying these operations. In other words, choose which digits to “move” (and they will then appear as their original value +1, capped at 9) and decide where to insert them so that when combined with the digits you did not move (which stay in their original order), the overall string is as small as possible in lexicographical order. Input A string s containing only digits. Output A new string that is lexicographically smallest. Examples Example 1: Input: s = "987" Output: "899" Example 2: Input: s = "1234" Output: "1234" Constraints The string length can be up to $10^5$. Example Input 987