Optimize Box IDs
Amazon● HardOAProblem statement
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
iand remove the digitboxIds[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.
Function
optimizeBoxIds(boxIds: String) → StringExamples
Example 1
boxIds = "26547"return = "24677"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
1 <= |boxIds| <= 2 * 10^5boxIdsconsists of only digits from 0 to 9. Note thatboxIdsis just a string consisting of digits, so leading zeros are allowed.