Leetcode 2259: Remove Digit From Number to Maximize Result

Input: The input consists of a string `number`, representing a positive integer, and a character `digit`, which is a digit to be removed from the string.

Example: number = '4598', digit = '5'

Constraints:

• 2 <= number.length <= 100

• number consists of digits from '1' to '9'.

• digit is a digit from '1' to '9'.

• digit occurs at least once in number.

Output: Return the resulting string after removing one occurrence of `digit` such that the value of the resulting string, when interpreted as an integer, is maximized.

Example: Output: '498'

Constraints:

Goal: The goal is to remove one occurrence of the specified `digit` to maximize the integer value of the resulting string.

Steps:

• Loop through the string to find the first occurrence of `digit` that, when removed, results in a larger number. This can be identified by checking the next character to see if it is larger than `digit`.

• If no such occurrence is found, remove the last occurrence of `digit` to ensure the maximum possible number.

Goal: Ensure that the solution efficiently handles strings up to 100 characters in length and only removes one occurrence of `digit`.

Steps:

• The string `number` will have a length between 2 and 100.

• There will be at least one occurrence of `digit` in `number`.

Assumptions:

• The string `number` will contain only digits from '1' to '9', and no leading zeros are allowed.

• Input: number = '4598', digit = '5'

• Explanation: After removing the '5' from the string '4598', the result is '498', which is the largest possible integer formed from the remaining digits.

• Input: number = '9871', digit = '1'

• Explanation: We can remove the '1' from '9871' to get '987', which is the maximum possible result.

Approach: The problem can be approached by iterating over the string to find the optimal digit to remove, ensuring that we maximize the remaining number.

Observations:

• We can remove any occurrence of `digit` but should focus on removing the first occurrence that leads to a larger number.

• We should aim to remove the first `digit` whose next character is greater than `digit`. If no such character exists, remove the last occurrence of `digit`.

Steps:

• Iterate over the string to find the first occurrence of `digit` that has a greater digit following it.

• If such an occurrence is found, remove `digit` at that position.

• If no such occurrence is found, remove the last occurrence of `digit` in the string.

Empty Inputs:

• There are no empty inputs as the string is guaranteed to have a length of at least 2.

Large Inputs:

• The solution should be efficient enough to handle strings with a length of up to 100 characters.

Special Values:

• Ensure that leading zeros are not generated after removing a digit.

Constraints:

• The string length is manageable, and the removal operation should be performed optimally to achieve the best possible result.

string removeDigit(string n, char digit) {
    for (int i = 0; i < n.size() - 1; ++i)
        if (n[i] == digit && n[i + 1] > digit)
            return n.substr(0, i) + n.substr(i + 1);
    int last_d = n.rfind(digit);
    return n.substr(0, last_d) + n.substr(last_d + 1);
}

1 : Function Declaration

string removeDigit(string n, char digit) {

This is the function signature. The function takes a string `n` and a character `digit` as input and returns a string with one occurrence of `digit` removed.

2 : For Loop Initialization

    for (int i = 0; i < n.size() - 1; ++i)

This loop iterates over the string `n` from the first character to the second last character, checking for the specified `digit`.

3 : Condition Check

        if (n[i] == digit && n[i + 1] > digit)

This condition checks if the current character is the `digit` and if the next character is greater than `digit`. If so, it identifies that this is the optimal place to remove the digit.

4 : Remove Digit

            return n.substr(0, i) + n.substr(i + 1);

If the condition is satisfied, the function removes the `digit` at index `i` and returns the modified string by concatenating the part before and after the digit.

5 : Find Last Occurrence

    int last_d = n.rfind(digit);

If no optimal digit is found in the loop, the function searches for the last occurrence of `digit` in the string using `rfind`.

6 : Remove Last Digit

    return n.substr(0, last_d) + n.substr(last_d + 1);

If no removal occurred in the loop, the function removes the last occurrence of the `digit` by using `substr` to exclude it from the string.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is linear because we iterate through the string to find the optimal position for removal and perform a string slicing operation.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is linear due to the need to store the modified string.

Leetcode 2259: Remove Digit From Number to Maximize Result

Explore →