FastPrepFastPrep
Problem Brief

Friendship String

OA

John and Mary, good friends, play a game to see how strong their friendship is. John gives Mary a tricky puzzle to solve. Here's how it goes:

Given a string s consisting of digits from 0 to 9 inclusive, You can choose a position i and delete a digit d on the ith position. Then Insert the digit min (d+1, 9) in any position (at the beginning, at the end or in between any two adjacent digits. What is the lexicographically smallest string you can get by performing these operations? A string 'a' is lexicographically smaller than a string 'b' of the same length of and only if the following holds: In the first position where a and b differ, the string 'a' has a smaller digit than the corresponding digit. Help Mary prove her friendship by solving the puzzle.

Input Format

The first line contains a single integer t -- the number of test cases. Then the test cases follow. Each test case consists of a single line that contains one string s. the string consisting of digits. Please note that s is just a string consisting of digits, so leading zeros are allowed.

Output Format

Print a single string the lexicographically smallest string that is possible to obtain.

1Example 1

Input
s = "415863388791991"
Output
"111334567888999"
Explanation

By performing the operations as per the rules, the lexicographically smallest string that can be obtained is "111334567888999".

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= t <= 1e4
  • 1 <= |s| <= 2 * 1e5
  • It's guaranteed that the sum of lengths of s over all test cases does not exceed 2 * 1e5.
    • public String friendshipString(String s) {
  // write your code here
}
    Input

    s

    "415863388791991"

    Output

    "111334567888999"

    Sign in to submit your solution.