Smallest number from a set of digits, with a lower bound

Part 1. You are given a non-empty list digits of single-digit integers (each 0-9). Use every element exactly once and arrange them to form the smallest possible non-negative integer. Return it as a string.

• The result must not have a leading zero. The one exception is the value zero itself, returned as "0".
• If every digit is 0, return "0".

def smallest_number(digits: list[int]) -> str: ...

Part 2. You are also given a non-negative integer bound as a decimal string, which may be longer than 64 bits. Return the smallest number that follows the Part 1 rules (all digits used once, no leading zero) and is strictly greater than bound. Return "" if there is none.

def smallest_greater_than(digits: list[int], bound: str) -> str: ...

Constraints: 1 <= len(digits) <= 10^5, 1 <= len(bound) <= 10^5. Aim for time linear in the input size.

Example 1

smallest_number([4, 0, 2, 0])  -> "2004"
smallest_number([0, 0, 0])     -> "0"

Example 2

smallest_greater_than([4, 0, 2, 0], "2040")  -> "2400"
smallest_greater_than([4, 0, 2, 0], "4200")  -> ""
smallest_greater_than([4, 0, 2, 0], "999")   -> "2004"

Reconstructed from the reported question; details may differ from what interviewers ask.