Clear Digits - Practice Coding Problems

Clear Digits - Problem

You are given a string s. Your task is to remove all digits by doing this operation repeatedly:

Delete the first digit and the closest non-digit character to its left.

Return the resulting string after removing all digits.

Note that the operation cannot be performed on a digit that does not have any non-digit character to its left.

Input & Output

Example 1 — Basic Case

$ Input: s = "abc3def2"

› Output: "abde"

💡 Note: First digit '3': remove '3' and closest left non-digit 'c' → "ab_def2". Next digit '2': remove '2' and closest left non-digit 'f' → "abde"

Example 2 — Digit Without Left Non-Digit

$ Input: s = "2ab3"

› Output: "a"

💡 Note: First digit '2': no non-digit to its left, remove only '2' → "ab3". Next digit '3': remove '3' and closest left non-digit 'b' → "a"

Example 3 — All Digits

$ Input: s = "123"

› Output: "123"

💡 Note: No non-digit characters exist, so no digits can be removed. Return original string

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters and digits

Visualization

Tap to expand

Understanding the Visualization

Input String

String with letters and digits mixed together

Remove Pairs

Each digit removes itself and closest left non-digit

Final Result

Remaining characters after all valid removals

Key Takeaway

🎯 Key Insight: Use a stack to naturally track the closest left non-digit for efficient removal

Asked in

M Microsoft 15 A Amazon 12

The key insight is that when we encounter a digit, we need to remove it along with the closest non-digit character to its left. A stack-based approach elegantly solves this by naturally maintaining access to the most recent non-digit character. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Solution	O(n)	O(n)	Use stack to track non-digits, pop when encountering digits
Brute Force Simulation	O(n²)	O(n)	Repeatedly find first digit and remove it with closest left non-digit

Stack-Based Solution — Algorithm Steps

Iterate through each character in the string
If character is not a digit, push to stack
If character is a digit, pop from stack (if not empty)
Convert remaining stack elements back to string

Visualization

Tap to expand

Step-by-Step Walkthrough

Push Non-Digits

Characters are pushed onto stack

Digit Pops Stack

When digit found, pop closest left non-digit

Continue

Stack contains final result

Code -

solution.c — C

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

char* solution(char* s) {
    int len = strlen(s);
    char* stack = (char*)malloc((len + 1) * sizeof(char));
    int top = 0;
    
    for (int i = 0; i < len; i++) {
        if (isdigit(s[i])) {
            // Remove the closest non-digit to the left (if exists)
            if (top > 0) {
                top--;
            }
        } else {
            // Add non-digit character to stack
            stack[top++] = s[i];
        }
    }
    
    stack[top] = '\0';
    return stack;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0; // Remove newline
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string, each character processed once

✓ Linear Growth

Space Complexity

O(n)

Stack can store up to n characters in worst case (no digits)

⚡ Linearithmic Space

29.8K 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

Stack-Based Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler