Teaching Kids Programming – Remove Digit From Number to Maximize Result

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a string number representing a positive integer and a character digit. Return the resulting string after removing exactly one occurrence of digit from number such that the value of the resulting string in decimal form is maximized. The test cases are generated such that digit occurs at least once in number.

Example 1:
Input: number = “123”, digit = “3”
Output: “12”
Explanation: There is only one ‘3’ in “123”. After removing ‘3’, the result is “12”.

Example 2:
Input: number = “1231”, digit = “1”
Output: “231”
Explanation: We can remove the first ‘1’ to get “231” or remove the second ‘1’ to get “123”.
Since 231 is greater than 123, we return “231”.
Example 3:

Input: number = “551”, digit = “5”
Output: “51”
Explanation: We can remove either the first or second ‘5’ from “551”.
Both result in the string “51”.

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:
The maximum length of number is really small.
Iterate through the digits of number and every time we see digit, try removing it.
To remove a character at index i, concatenate the substring from index 0 to i – 1 and the substring from index i + 1 to number.length – 1.

Algorithm to Remove Digit From Number to Maximize Result

To remove a character at index i from a string s – we can use the string concatenation: s[:i]+s[i+1:]. With this, we can go through (using enumerate function) the digits and check each possible deletion.

1
2
3
4
5
6
7

class Solution:
    def removeDigit(self, number: str, digit: str) -> str:        
        ans = ""
        for i,j in enumerate(number):
            if j == digit:
                ans = max(ans, number[:i] + number[i+1:])
        return ans if ans else number

class Solution:
    def removeDigit(self, number: str, digit: str) -> str:        
        ans = ""
        for i,j in enumerate(number):
            if j == digit:
                ans = max(ans, number[:i] + number[i+1:])
        return ans if ans else number

Time complexity for this Bruteforce algorithm is O(N). We can do this in one liner:

1
2
3

class Solution:
    def removeDigit(self, number: str, digit: str) -> str:        
        return max((number[:i] + number[i+1:] for i,j in enumerate(number) if j == digit), default = number)

class Solution:
    def removeDigit(self, number: str, digit: str) -> str:        
        return max((number[:i] + number[i+1:] for i,j in enumerate(number) if j == digit), default = number)

If the digit is not found in the number string, we return itself by supplying a default parameter for the max function.

–EOF (The Ultimate Computing & Technology Blog) —