Build the Largest Allowed Number Below a Limit
Company: Bytedance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
## Build the Largest Allowed Number Below a Limit
### Problem
Implement `largestAllowedBelow(limit, digits) -> result`.
`limit` is a positive decimal integer represented as a string. The values in `digits` may be reused any number of times. Return the canonical decimal string for the largest nonnegative integer strictly smaller than `limit` that can be written using only allowed digits. Return the string `"-1"` when no such integer exists.
### Portable Contract
- `limit` contains only decimal digits, has no leading zero, and satisfies `1 <= limit.length <= 90,000`.
- `digits` contains between 1 and 10 integers. Every value is from `0` through `9`; duplicate entries have no additional effect.
- An ordinary result has no leading zero unless it is exactly `"0"`.
- Every occurrence of an allowed digit may be used again, including zero.
- The comparison with `limit` is numeric and strict. Returning `limit` itself is not allowed.
- Do not convert the complete `limit` to a fixed-width numeric type and do not modify either input.
- Let `B` be the compact UTF-8 JSON byte length of `[limit,digits]`, counting brackets, commas, quotes, and digit characters. Inputs satisfy `B <= 96,000`.
- Let `R` be the compact UTF-8 JSON byte length of the returned string. Because a valid result has at most `limit.length` digits, `R <= 90,002`; input plus result is at most `186,002` bytes.
- For `n = limit.length` and `d` distinct allowed digits, target `O(n log d + d log d)` time and `O(n + d)` auxiliary space, including the returned string.
The contract projects without numeric precision loss to all four languages:
- Python: `def largestAllowedBelow(limit: str, digits: list[int]) -> str`
- JavaScript: `function largestAllowedBelow(limit, digits)` returns a string.
- Java: `String largestAllowedBelow(String limit, List<Integer> digits)`
- C++: `string largestAllowedBelow(const string& limit, const vector<int>& digits)`
```hint Compare prefixes as strings
A candidate with the same length as the limit remains viable only while its chosen prefix does not exceed the corresponding limit prefix.
```
```hint Recover from a blocked suffix
When no allowed digit can continue the current prefix, reconsider an earlier position that can be made smaller before filling later positions.
```
### Examples
```text
limit = "23415"
digits = [2, 4, 9]
result = "22999"
```
```text
limit = "1000"
digits = [0, 1]
result = "111"
```
### Discussion Requirements
1. Explain how the method distinguishes a same-length candidate from the best shorter candidate.
2. Cover a prefix that matches for several positions before backtracking, a limit that itself uses only allowed digits, and a digit set containing only zero.
3. Handle duplicate allowed digits, a one-digit limit, an impossible result, and the rule against leading zeros.
4. Explain why decimal-string comparison avoids overflow and precision differences across the four languages.
Quick Answer: Construct the greatest canonical decimal number below a very large limit using only a reusable set of allowed digits. It calls for string-based numeric reasoning, strict comparison, leading-zero rules, blocked-prefix recovery, impossible cases, and scalable performance.
Implement `largestAllowedBelow(limit, digits)`.
`limit` is a positive decimal integer given as a **string**, and `digits` lists the decimal digits you are allowed to write. Every allowed digit may be reused any number of times, including zero times. Return the canonical decimal string for the **largest nonnegative integer strictly smaller than `limit`** that can be written using only allowed digits, or the string `"-1"` when no such integer exists.
"Largest" names exactly one integer, so the answer is unique.
### Output rules
- The return value is always a string, never a number.
- An ordinary answer has **no leading zero**. The one exception is the integer zero, whose canonical form is exactly `"0"` -- never `""` and never `"00"`.
- The comparison with `limit` is numeric and **strict**. Returning `limit` itself is never allowed, even when every digit of `limit` happens to be allowed.
- Return exactly `"-1"` when no allowed-digit integer is strictly below `limit`. Do not return an empty string and do not raise.
- Duplicate entries in `digits` have no additional effect: `[2, 2, 9]` allows exactly what `[2, 9]` allows.
- Do not modify `limit` or `digits`.
- `limit` can be far longer than any fixed-width integer type, so do not parse it into `int`, `long`, `long long`, or a floating-point value; compare decimal strings position by position instead. Nothing numeric crosses the function boundary: `limit` and the result are strings, and every entry of `digits` is a single digit `0`-`9`.
### Constraints
- `limit` contains only decimal digits, has no leading zero, and satisfies `1 <= limit.length <= 90,000`. It always represents a positive integer, so `limit >= 1`.
- `digits` contains between 1 and 10 integers. Every value is from `0` through `9`; duplicate entries have no additional effect, and `digits` is never empty.
- Let `B` be the compact UTF-8 JSON byte length of `[limit, digits]`, counting brackets, commas, quotes, and digit characters. Inputs satisfy `B <= 96,000`.
- Let `R` be the compact UTF-8 JSON byte length of the returned string. A valid result has at most `limit.length` digits, so `R <= 90,002`, and input plus result is at most `186,002` bytes.
- For `n = limit.length` and `d` distinct allowed digits, target `O(n log d + d log d)` time and `O(n + d)` auxiliary space, including the returned string.
### Examples
**Example 1**
```text
limit = "23415"
digits = [2, 4, 9]
result = "22999"
```
The answer keeps the leading `2`, then drops below the limit at index 1 -- `3` is not allowed, and the largest allowed digit under `3` is `2` -- and fills every remaining position with the largest allowed digit `9`. `22999 < 23415`, and nothing writable from `{2, 4, 9}` sits between them.
**Example 2**
```text
limit = "1000"
digits = [0, 1]
result = "111"
```
No four-digit answer exists: `1000` itself is barred by strictness, and every other four-digit string over `{0, 1}` either exceeds `1000` or starts with `0`. The best three-digit string over `{0, 1}` is `111`.
Constraints
- `limit` contains only decimal digits, has no leading zero, and satisfies 1 <= limit.length <= 90,000; it always represents a positive integer, so limit >= 1
- `digits` contains between 1 and 10 integers, every value from 0 through 9; duplicate entries have no additional effect, so `digits` is never empty and the distinct-digit count d satisfies 1 <= d <= 10
- Every allowed digit may be reused any number of times, including zero times
- The answer is the largest nonnegative integer strictly below `limit` writable with only allowed digits; the comparison is numeric and strict, so returning `limit` itself is never allowed
- An ordinary answer has no leading zero; the single exception is the integer zero, whose canonical form is exactly "0"
- Return exactly the string "-1" when no such integer exists
- Neither `limit` nor `digits` may be modified, and `limit` must never be converted to a fixed-width numeric type
- Let B be the compact UTF-8 JSON byte length of [limit, digits], counting brackets, commas, quotes, and digit characters. Inputs satisfy B <= 96,000
- Let R be the compact UTF-8 JSON byte length of the returned string. A valid result has at most limit.length digits, so R <= 90,002, and input plus result is at most 186,002 bytes
- For n = limit.length and d distinct allowed digits, target O(n log d + d log d) time and O(n + d) auxiliary space, including the returned string
Examples
Input: ('23415', [2, 4, 9])
Expected Output: '22999'
Explanation: Worked example 1. Index 0 matches the limit's `2`; index 1 cannot, because `3` is not allowed, so the answer drops to the largest allowed digit under `3` (that is `2`) and fills the rest with the largest allowed digit `9`.
Input: ('1000', [0, 1])
Expected Output: '111'
Explanation: Worked example 2. No four-digit answer exists: `1000` itself is barred by strictness and every other four-digit string over {0,1} either exceeds 1000 or starts with `0`, so the best three-digit string wins.
Hints
- A same-length answer agrees with `limit` on some prefix and then drops strictly below it at exactly one position, filling everything after that position freely. Which prefix length makes the answer largest, and what has to be true of `limit`'s own digits for a prefix of that length to be reachable at all?
- When no allowed digit can continue the current prefix, the fix is not to give up -- it is to reconsider an earlier position that can still be made smaller. Scanning candidate drop positions from right to left answers 'which is the latest one that works?' in a single pass.
- Some limits admit no same-length answer at all (try `limit = "1000"` with `digits = [0, 1]`). What is the largest number with one fewer digit, and what extra rule does its leading position have to respect that an interior position does not?