Build the Largest Allowed Number Below a Limit

Problem Statement

Given a limit N as a string and an array of integers digits, construct the largest possible integer less than N using only the provided digits. If no such number can be formed, return an empty string.

You may use each digit from the provided digits array as many times as you like. Note that the resulting number cannot have leading zeros unless the number itself is exactly "0" (though the problem requires the result to be strictly less than N).

Function Signature

def find_largest_less_than_n(n: str, digits: List[int]) -> str:

Examples

Example 1: Input: n = "231", digits = [2, 4, 9] Output: "229" Explanation: 229 is the largest number less than 231 using only {2, 4, 9}.

Example 2: Input: n = "1000", digits = [5, 7] Output: "777" Explanation: The largest number with fewer digits than N is always smaller than N, provided it uses the largest allowed digits.

Constraints

• n length: 1 to 18 digits.
• digits: non-empty, contains distinct integers between 0-9.
• The result should be returned as a string.

Edge Cases

• What happens if the largest possible number has fewer digits than n? (e.g., if n=100 and all allowed digits are 9, the result is 99).
• Handle cases where no number can be formed (e.g., n=10, digits=[5], but only one digit is allowed and nothing fits).