FastPrepFastPrep
Problem Brief

Best Way to Pack

FULLTIMEOA
See Amazon online assessment and hiring insights

SDE II

The team at a TomTom International factory has been assigned a critical optimization task aimed at improving the efficiency of packing a set of boxes, each labeled with a unique ID. These boxes are initially arranged in a single row from left to right, where the ID of the i-th box is represented by the string s_id, which consists of digits ranging from 0 to 9, inclusive.

To streamline the packing process, the team has been granted the ability to perform a specific operation an arbitrary number of times, including zero times if necessary. The operation is defined as follows:

  • The team can choose any index within the string s_id and remove the digit at that position.
  • After removing the selected digit, the team can insert a new box with an updated ID. The new ID is determined by computing min(s_id[i] + 1, 9), ensuring that the new ID does not exceed 9.

    • Given the initial arrangement of boxes represented by the string s_id, the goal is to determine the lexicographically minimal string that can be achieved by applying the allowed operations optimally.

    Clarification on Lexicographic Order:

    A string X is considered lexicographically smaller than another string Y of the same length if and only if, at the first position where X and Y differ, the corresponding digit in X is smaller than the corresponding digit in Y.

    Objective: Find and return the lexicographically smallest possible string that can be formed by performing the given operation any number of times.

    1Example 1

    Input
    id = "26547"
    Output
    "24677"
    Explanation
    Example 1 illustration
    Hence, the string returned is "24677". It can be proved that this is the lexicographically minimal string possible.

    2Example 2

    Input
    id = "34892"
    Output
    "24599"
    Explanation
    Example 2 illustration
    It is said to be 24599 with no explanation.. This test caes was added on 04-13-2025.
    public String bestWayToPack(String id) {
  // write your code here
}
    Input

    id

    "26547"

    Output

    "24677"

    Sign in to submit your solution.