Coding questions · Cohere

Delete One '5' From a Digit String to Get the Largest Number

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.

Function Signature

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.

Largest Number After Removing One Five

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?

Approach

Deleting the '5' at index i shifts every later digit one position left. Compare deleting at i with deleting a later '5' at j: both results agree on the prefix before i, and at position i the first result holds digits[i+1] while the second still holds '5'. So if digits[i+1] > '5', deleting at i beats every later deletion, and deleting at an earlier '5' that is not followed by a larger digit is never better. Therefore scan left to right and delete the first '5' whose next character is greater than '5'. If no such '5' exists, every earlier deletion either ties or loses (it moves a smaller-or-equal digit into a higher position), so deleting the last '5' is optimal. The result is built by string slicing, which keeps any leading zeros and never converts the value to an integer.

Time complexity: O(n)
Space complexity: O(n)