Delete One '5' From a Digit String to Get the Largest Number
Company: Cohere
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a string `digits` made up of decimal digits that contains at least one `'5'`. Delete exactly one occurrence of the character `'5'` from `digits` and return the resulting string whose numeric value is as large as possible.
### Function Signature
```python
def max_after_deleting_five(digits: str) -> str:
```
### Rules
- Exactly one `'5'` is deleted. No other character is removed, added or reordered.
- Every possible result has length `len(digits) - 1`, so comparing two results numerically is the same as comparing them character by character from the left.
- The returned string keeps any leading zeros the deletion produces. For example, deleting the only `'5'` from `"503"` returns `"03"`.
- Different deletions can produce the same string (either `'5'` in `"55"` gives `"5"`). The answer is that string, so the output is always unique.
### Constraints
- `2 <= len(digits) <= 100000`
- Every character of `digits` is one of `'0'` through `'9'`.
- `digits[0] != '0'`
- `digits` contains at least one `'5'`.
### Examples
**Example 1**
- Input: `digits = "15958"`
- Output: `"1958"`
- Explanation: Deleting the `'5'` at index 1 gives `"1958"`, and deleting the `'5'` at index 3 gives `"1598"`. The larger value is `"1958"`.
**Example 2**
- Input: `digits = "5505"`
- Output: `"550"`
- Explanation: Deleting the `'5'` at index 0 or index 1 gives `"505"`, and deleting the `'5'` at index 3 gives `"550"`, which is larger.
**Example 3**
- Input: `digits = "503"`
- Output: `"03"`
- Explanation: There is only one `'5'`. Deleting it leaves `"03"`, and the leading zero is kept.
Overview: Given a digit string containing at least one 5, delete exactly one 5 so the remaining string has the largest possible numeric value, keeping any leading zeros. This intern online-assessment problem tests reasoning about how each digit position affects a number and careful handling of repeated digits.
You are given a string `digits` made up of decimal digits that contains at least one `'5'`. Delete **exactly one** occurrence of the character `'5'` from `digits` and return the resulting string whose numeric value is as large as possible.
Implement `max_after_deleting_five(digits)`.
**Rules**
- Exactly one `'5'` is deleted. No other character is removed, added or reordered.
- Every possible result has length `len(digits) - 1`, so comparing two results numerically is the same as comparing them character by character from the left.
- The returned string keeps any leading zeros the deletion produces. For example, deleting the only `'5'` from `"503"` returns `"03"`.
- Different deletions can produce the same string (either `'5'` in `"55"` gives `"5"`). The answer is that string, so the output is always unique.
- `digits` can be up to 100,000 characters long, so its numeric value can be far larger than any built-in integer type; treat it as a string.
**Example 1**
Input: `digits = "15958"`
Output: `"1958"`
Explanation: Deleting the `'5'` at index 1 gives `"1958"`, and deleting the `'5'` at index 3 gives `"1598"`. The larger value is `"1958"`.
**Example 2**
Input: `digits = "5505"`
Output: `"550"`
Explanation: Deleting the `'5'` at index 0 or index 1 gives `"505"`, and deleting the `'5'` at index 3 gives `"550"`, which is larger.
**Example 3**
Input: `digits = "503"`
Output: `"03"`
Explanation: There is only one `'5'`. Deleting it leaves `"03"`, and the leading zero is kept.
Constraints
- 2 <= len(digits) <= 100000
- Every character of digits is one of '0' through '9'.
- digits[0] != '0'
- digits contains at least one '5'.
Examples
Input: ("15958",)
Expected Output: "1958"
Input: ("5505",)
Expected Output: "550"
Hints
- Compare deleting the '5' at index i with deleting a later '5' at index j: the two results agree before i. Where do they first differ?
- Removing a '5' pulls its right neighbour one position to the left. When does that make the number bigger at the earliest possible position?
- If no '5' ever benefits from being removed in that way, which '5' costs the least to remove?