algoadvance

You are given a string number representing a positive integer and a character digit. You need to remove exactly one occurrence of the digit from the number so that the resulting string represents the largest possible integer. Return the resulting string.

Example

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

Input: number = "551", digit = '5'
Output: "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.

Clarifying Questions

1. Q: Are there any leading zeros in the number? A: No, since the number is always a positive integer, it will not have leading zeros.

2. Q: Are there multiple occurrences of digit in the number? A: Yes, there can be multiple occurrences and you need to find which occurrence to remove to maximize the resultant integer.

Strategy

1. Iterate Through the Number:
   • We will iterate through each character in the number.
2. Generate Possible Numbers:
   • At each occurrence of digit, we will create a new string that omits that occurrence.
   • Keep track of these generated numbers.
3. Find the Maximum:
   • Compare the generated numbers and return the largest one.

Code

Here is a Python solution for the problem:

def removeDigit(number: str, digit: str) -> str:
    possible_results = []

    for i, num in enumerate(number):
        if num == digit:
            # Create a new number by omitting the current occurrence of the digit
            new_number = number[:i] + number[i+1:]
            possible_results.append(new_number)
    
    # Return the maximum of the possible results lexicographically
    return max(possible_results)

# Example Usage
print(removeDigit("1231", '1'))  # Output: "231"
print(removeDigit("551", '5'))   # Output: "51"

Time Complexity

• Iteration Through the Number: O(n) where n is the length of the number.
• Creating New Strings: Each string creation is O(n) due to slicing.

The time complexity is O(n^2) in the worst case, where you have to slice strings multiple times. However, since the length of number is constrained to be at most 100, this is manageable.

Try our interview co-pilot at AlgoAdvance.com

• 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?