Remove Digit From Number to Maximize Result

Remove Digit From Number to Maximize Result - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: number = "123", digit = "3"

› Output: "12"

💡 Note: Only one occurrence of '3' at the end. Removing it gives "12".

Example 2 — Multiple Occurrences

$ Input: number = "1231", digit = "1"

› Output: "231"

💡 Note: Two occurrences of '1' at positions 0 and 3. Removing position 0 gives "231", removing position 3 gives "123". "231" > "123", so return "231".

Example 3 — Remove for Maximum

$ Input: number = "551", digit = "5"

› Output: "51"

💡 Note: Two occurrences of '5'. Removing first gives "51", removing second gives "55". "55" > "51", but we want to maximize by removing the optimal occurrence, which is the first one to get "51".

Constraints

1 ≤ number.length ≤ 1000
number consists of digits
digit is a digit character
digit occurs at least once in number

Visualization

Tap to expand

Key Insight: Remove the digit that maximizes the remaining number

Understanding the Visualization

Input

String number and target digit to remove

Process

Find optimal position to remove target digit

Output

Maximum possible number after removal

Key Takeaway

🎯 Key Insight: Remove the first occurrence where the next digit is larger to maximize the result

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to remove the first occurrence of the target digit where the next digit is larger, or the last occurrence if no such position exists. The greedy approach achieves this in a single pass. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Removal	O(n)	O(1)	Remove the first occurrence where the next digit is larger
Try All Removals	O(n²)	O(n)	Remove each occurrence of the digit and find the maximum result

Greedy Removal — Algorithm Steps

Scan left to right for target digit
If next digit is larger, remove current occurrence
If no such position, remove the last occurrence

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Left to Right

Look for target digit from left

Check Next Digit

If next digit is larger, remove current

Create Result

Build final string without removed digit

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* number, char* digit) {
    int len = strlen(number);
    char target = digit[0];
    char* result = malloc(len);
    
    for (int i = 0; i < len; i++) {
        if (number[i] == target) {
            // If this is the last character or next character is larger
            if (i == len - 1 || number[i + 1] > target) {
                strncpy(result, number, i);
                result[i] = '\0';
                strcat(result, number + i + 1);
                return result;
            }
        }
    }
    
    // This should never happen based on problem constraints
    strcpy(result, number);
    return result;
}

int main() {
    char number[1000], digit[2];
    fgets(number, sizeof(number), stdin);
    number[strcspn(number, "\n")] = 0;
    fgets(digit, sizeof(digit), stdin);
    digit[strcspn(digit, "\n")] = 0;
    
    char* result = solution(number, digit);
    printf("%s\n", result);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string to find the optimal removal position

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables, no extra data structures

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Removal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler