algoadvance

Leetcode 2259. Remove Digit From Number to Maximize Result

Problem Statement

You are given a string number representing a positive integer and a character digit. Your task is to remove exactly one occurrence of digit from number so that the resulting value is the largest possible.

Return the resulting string representing the largest possible value.

Example

• Example 1:

  Input: number = "123", digit = "3"
  Output: "12"
  

• Example 2:

  Input: number = "1231", digit = "1"
  Output: "231"
  

• Example 3:

  Input: number = "551", digit = "5"
  Output: "51"
  

Clarifying Questions

1. Q: Can digit appear multiple times in number? A: Yes, digit can appear multiple times in number.

2. Q: What constraints should we consider regarding the length of number? A: Typically, constraints would be mentioned in the problem. Assuming reasonable constraints (like number not longer than 10⁵).

3. Q: Is the input always a valid positive integer string and a single digit character? A: Yes, the input constraints ensure number is a non-empty string of digits ('0'-'9') and digit is a single character digit ('0'-'9').

Strategy

1. Iterate over the string number and identify all occurrences of digit.
2. For every identified occurrence, create a new potential result by removing that occurrence of digit.
3. Track the maximum value string seen so far.
4. Return the maximum value string after all iterations.

Code

Here’s the C++ implementation of the above strategy:

#include <string>

std::string removeDigit(std::string number, char digit) {
    std::string maxResult = "";
    
    for (size_t i = 0; i < number.size(); ++i) {
        if (number[i] == digit) {
            // Create a new string without the i-th occurrence of 'digit'
            std::string newNumber = number.substr(0, i) + number.substr(i + 1);
            
            // Check if it's the largest we've seen
            if (newNumber > maxResult) {
                maxResult = newNumber;
            }
        }
    }
    
    return maxResult;
}

Time Complexity

The time complexity of this solution is (O(n^2)) where (n) is the length of number:

• We iterate over number once, so (O(n)).
• For each digit removal, we perform string concatenation, which in the worst case takes (O(n)).

Edge Cases

• When digit appears at the beginning, middle, or end of the string.
• Handling large sizes of number efficiently.

Testing

We should test the function with the following cases:

1. Single occurrence of digit.
2. Multiple occurrences of digit.
3. number being at its minimal size (e.g., “1” and digit=”1”).

This provides a robust check across the range of expected inputs.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?