FastPrepFastPrep
Problem Brief

Optimize Box IDs

OA

The team at an Amazon warehouse is given a task to optimize the packing of a set of boxes with different IDs.

Each box is labeled with an ID, and these boxes are currently arranged in a single row from left to right, where the ID of the i-th box is represented by the string boxIds consisting of digits from 0 to 9 inclusive.

To make the packing more efficient, the team can perform the following operation any (possibly zero) number of times:

  • Choose an index i and remove the digit boxIds[i].
  • Then insert the box with ID min(boxIds[i] + 1, 9) on any position (at the beginning, at the end, or in between any two adjacent boxes) in the row.

Given a string boxIds, find the lexicographically minimal string of boxes using these operations.

Note: A string X is lexicographically smaller than a string Y of the same length if and only if: In the first position where X and Y differ, the string X has a smaller digit than the corresponding digit in Y.

1Example 1

Input
boxIds = "26547"
Output
"24677"
Explanation
Delete 5 and insert 6 in the 4th position of the string → Delete 6 from the 2nd position and insert 7 in the 4th position of the string. Hence, the string returned is "24677". It can be proved that this is the lexicographically minimal string possible.

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= |boxIds| <= 2 * 10^5
  • boxIds consists of only digits from 0 to 9. Note that boxIds is just a string consisting of digits, so leading zeros are allowed.
    • public String optimizeBoxIds(String boxIds) {
  // write your code here
}
    Input

    boxIds

    "26547"

    Output

    "24677"

    Sign in to submit your solution.