Problem Description

You are given a string number that represents a positive integer and a character digit.

Your task is to remove exactly one occurrence of the character digit from the string number. After removing this digit, the remaining characters form a new number. You need to choose which occurrence of digit to remove such that the resulting number is as large as possible.

For example, if number = "1231" and digit = "1", you have two choices:

• Remove the first "1" to get "231"
• Remove the second "1" to get "123"

Since "231" is larger than "123", you would return "231".

The problem guarantees that the character digit appears at least once in the string number, so there will always be at least one valid removal option.

The solution approach iterates through each position in the string where digit appears, creates a new string by removing that occurrence (concatenating the part before and after that position), and returns the maximum value among all possible results.

Intuition

Since we need to remove exactly one occurrence of a specific digit to maximize the resulting number, we need to think about which occurrence to remove when the digit appears multiple times.

The key insight is that when comparing numbers as strings, they are compared lexicographically (character by character from left to right). For example, "231" > "123" because at the first position, '2' > '1'.

Given that we must remove one digit, we have a finite number of choices - we can only remove from positions where our target digit appears. If the digit appears k times, we have exactly k different possible results.

Rather than trying to devise a clever rule about which occurrence to remove (which could get complicated considering various edge cases), we can leverage the fact that we have limited options. We can simply:

1. Try removing the digit from each position where it appears
2. Generate all possible resulting strings
3. Compare them and pick the maximum

This brute force approach works efficiently because:

• The number of positions to check is at most the length of the string
• String comparison in Python naturally gives us the lexicographically largest string
• Using the max() function with a generator expression makes the code concise and readable

The beauty of this solution is its simplicity - instead of overthinking the problem with complex logic about when to remove which digit, we let Python's built-in max() function handle the comparison for us.

Learn more about Greedy patterns.

Solution Approach

The solution uses a brute force enumeration approach combined with Python's built-in string manipulation and comparison capabilities.

Algorithm Steps:

1. Enumerate all positions: We iterate through each position i in the string number using enumerate(), which gives us both the index and the character at that position.

2. Filter target digit positions: We only consider positions where the character d equals our target digit. This is done using the condition if d == digit in the generator expression.

3. Generate candidate strings: For each valid position i where number[i] == digit, we create a new string by:

   • Taking the prefix: number[:i] (all characters before position i)
   • Taking the suffix: number[i + 1:] (all characters after position i)
   • Concatenating them: number[:i] + number[i + 1:]

   This effectively removes the character at position i.

4. Find maximum: We use Python's max() function to find the lexicographically largest string among all candidates. Since strings are compared character by character from left to right, this gives us the numerically largest result.

Example walkthrough:

If number = "1231" and digit = "1":

• Position 0: d = "1" matches, generate "" + "231" = "231"
• Position 1: d = "2" doesn't match, skip
• Position 2: d = "3" doesn't match, skip
• Position 3: d = "1" matches, generate "123" + "" = "123"
• Return max(["231", "123"]) = "231"

The time complexity is O(n²) where n is the length of the string, as we potentially create n new strings, each of length n-1. The space complexity is O(n²) in the worst case if all characters are the target digit.

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Example: number = "52352" and digit = "5"

We need to remove exactly one occurrence of "5" to get the largest possible number.

Step 1: Identify positions where digit appears

• Position 0: "5" ✓ (matches our target digit)
• Position 1: "2" ✗ (not our target)
• Position 2: "3" ✗ (not our target)
• Position 3: "5" ✓ (matches our target digit)
• Position 4: "2" ✗ (not our target)

So digit "5" appears at positions 0 and 3.

Step 2: Generate all possible results by removing each occurrence

For position 0 (remove first "5"):

• Prefix: number[:0] = ""
• Suffix: number[1:] = "2352"
• Result: "" + "2352" = "2352"

For position 3 (remove second "5"):

• Prefix: number[:3] = "523"
• Suffix: number[4:] = "2"
• Result: "523" + "2" = "5232"

Step 3: Compare all candidates and select maximum

We have two candidates: "2352" and "5232"

Comparing lexicographically (character by character):

• First character: "2" vs "5" → "5" is greater
• Therefore "5232" > "2352"

Final Answer: "5232"

This demonstrates why we need to check all positions - removing the first occurrence gives "2352", but removing the second occurrence gives us the larger result "5232". The algorithm correctly identifies this by trying both removals and selecting the maximum.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The code iterates through the string number to find all occurrences of the target digit. For each occurrence found, it creates a new string by concatenating number[:i] and number[i+1:], which takes O(n) time for string slicing and concatenation. If there are k occurrences of the digit (where k ≤ n), we create k strings, each requiring O(n) time. After generating all possible strings, the max() function compares them, which takes O(k * n) time since string comparison is O(n). Therefore, the overall time complexity is O(k * n) = O(n²) in the worst case when k approaches n.

Space Complexity: O(n²)

The generator expression creates up to k strings, where each string has length n-1. In the worst case, when all characters are the target digit, we would have n strings of length n-1, requiring O(n * (n-1)) = O(n²) space. However, since we're using a generator expression with max(), Python needs to store all generated strings in memory simultaneously to perform the comparison. Additionally, each string slice operation creates a new string object. Therefore, the total space complexity is O(n²).

Note: The reference answer states space complexity as O(n), which would be true if only considering the space for a single string at a time. However, the max() function needs to materialize all strings from the generator to compare them, leading to O(n²) space usage.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Attempting Numerical Comparison Instead of String Comparison

A common mistake is trying to convert the resulting strings to integers for comparison, which can lead to overflow issues with very large numbers or unnecessary complexity.

Incorrect approach:

def removeDigit(self, number: str, digit: str) -> str:
    candidates = []
    for i, d in enumerate(number):
        if d == digit:
            candidates.append(int(number[:i] + number[i + 1:]))
    return str(max(candidates))

Why it's problematic:

• Python integers can handle arbitrarily large numbers, but this adds unnecessary conversion overhead
• In other languages, this could cause integer overflow for very long number strings
• String comparison naturally gives us the lexicographically largest result, which corresponds to the numerically largest value for strings of the same length

Solution: Stick with string comparison as shown in the original solution. Python's string comparison works left-to-right, character by character, which correctly identifies the largest numerical value.

Pitfall 2: Greedy Approach - Removing First Occurrence Where Next Digit is Larger

A tempting optimization is to use a greedy approach: find the first occurrence of the target digit where the next character is larger, or remove the last occurrence if no such position exists.

Incorrect greedy approach:

def removeDigit(self, number: str, digit: str) -> str:
    last_index = -1
    for i in range(len(number)):
        if number[i] == digit:
            last_index = i
            # If next digit is larger, remove current digit immediately
            if i < len(number) - 1 and number[i] < number[i + 1]:
                return number[:i] + number[i + 1:]
    # If no increasing pattern found, remove the last occurrence
    return number[:last_index] + number[last_index + 1:]

Why it works (and when to use it): This greedy approach actually produces the correct answer and is more efficient with O(n) time complexity. The logic is:

• If we find a target digit followed by a larger digit, removing it immediately maximizes the result
• If no such position exists, removing the rightmost occurrence minimizes the impact on the larger place values

When to choose each approach:

• Use the brute force approach when code simplicity and readability are priorities, or when the string length is small
• Use the greedy approach when optimizing for performance with longer strings

Both solutions are valid, but understanding the trade-off between simplicity and efficiency is crucial for interview discussions.