Remove Digit From Number to Maximize Result

Easy
1196.

Remove Digit From Number to Maximize Result

Remove Digit From Number to Maximize Result is an easy coding problem on strings, greedy and enumeration, asked in Amazon and Microsoft interviews.

You are given a positive integer as a string number and a single character digit that occurs in number at least once.

Remove exactly one occurrence of digit from number so that the remaining string, read as a decimal number, is as large as possible. Return that remaining string.

Example 1

Input
number = "1231", digit = "1"
Output
231
Explanation
Removing the first `1` gives 231; removing the last gives 123.

Example 2

Input
number = "551", digit = "5"
Output
51
Explanation
Either `5` gives the same result.

Example 3

Input
number = "9479", digit = "9"
Output
947

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} number
 * @param {string} digit
 * @return {string}
 */
var removeDigit = function(number, digit) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove Digit From Number to Maximize Result — Solution

Remove Digit From Number to Maximize Result solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Remove Digit From Number to Maximize Result is an easy coding problem on strings, greedy and enumeration, asked in Amazon and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Strings, Greedy, Enumeration
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a positive integer as a string number and a single character digit that occurs in number at least once.

Remove exactly one occurrence of digit from number so that the remaining string, read as a decimal number, is as large as possible. Return that remaining string.

Example 1

Input: number = "1231", digit = "1"
Output: 231
Explanation: Removing the first `1` gives 231; removing the last gives 123.

Example 2

Input: number = "551", digit = "5"
Output: 51
Explanation: Either `5` gives the same result.

Example 3

Input: number = "9479", digit = "9"
Output: 947

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

Hints for Remove Digit From Number to Maximize Result

  1. Hint 1

    Every candidate has the same length, so comparing them as strings compares them as numbers.

  2. Hint 2

    Trying each occurrence and keeping the best already works for 100 digits.

  3. Hint 3

    Greedy: remove the first occurrence that is followed by a larger digit — that raises the earliest possible position. If no such occurrence exists, remove the last one.

How to solve Remove Digit From Number to Maximize Result

Removing digit at index i shifts the next character into position i. The result grows at the earliest position possible when that next character is larger than digit, so the best choice is the first such occurrence; if every occurrence is followed by a smaller-or-equal digit (or nothing), removing the last occurrence disturbs the number as late as possible.

Approach

  1. Scan number from left to right, remembering the index last of each occurrence of digit.
  2. At an occurrence i with number[i+1] > digit, stop and remove index i.
  3. If the scan finishes, remove index last.
  4. Return the string without that character.

Why it works

Two candidates that remove occurrences i < j agree before position i; at position i the first has number[i+1] and the second still has digit. If number[i+1] > digit the first is larger, and choosing the earliest such i beats every later removal. If number[i+1] < digit the first is smaller, so a later removal wins; if they are equal the comparison moves on in the same way. Hence, without an improving occurrence, the last occurrence is best. The simple alternative — build all candidates and keep the largest — is also correct at these sizes.

Complexity

  • Time — O(n)
  • Space — O(n) for the result

Pitfalls

  • Do not convert to an integer: 100 digits overflow every fixed-width type.
  • Removing the first occurrence is not always right ("9479" with 9).
  • With no improving occurrence, remove the last occurrence, not the first.

Reference solution

Python

def removeDigit(number: str, digit: str) -> str:
    last = -1
    for i, c in enumerate(number):
        if c == digit:
            last = i
            if i + 1 < len(number) and number[i + 1] > digit:
                break
    return number[:last] + number[last + 1:]

Java

public static String removeDigit(String number, String digit) {
    char d = digit.charAt(0);
    int idx = -1;
    for (int i = 0; i < number.length(); i++) {
        if (number.charAt(i) == d) {
            idx = i;
            if (i + 1 < number.length() && number.charAt(i + 1) > d) break;
        }
    }
    return number.substring(0, idx) + number.substring(idx + 1);
}

C++

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

JavaScript

var removeDigit = function(number, digit) {
    var idx = -1;
    for (var i = 0; i < number.length; i++) {
        if (number[i] === digit) {
            idx = i;
            if (i + 1 < number.length && number[i + 1] > digit) break;
        }
    }
    return number.slice(0, idx) + number.slice(idx + 1);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms