Clear Digits - Solution & Explanation

Problem Overview: You receive a string containing lowercase letters and digits. Every digit removes itself and the closest non-digit character to its left. After processing the entire string, return the remaining characters.

The key observation: each digit cancels exactly one previous letter. You never need to search far or reorder characters. A structure that supports removing the most recent character works perfectly. This turns the problem into a simple simulation.

Approach 1: Stack-Based Simulation (O(n) time, O(n) space)

Use a stack to keep track of the letters that are still valid. Iterate through the string once. When you encounter a letter, push it onto the stack. When you encounter a digit, pop the top character from the stack because that digit removes the closest letter to its left. This mirrors the rule exactly: the most recent letter is always the one removed.

After the scan completes, the stack contains only the characters that survived all digit removals. Join the stack into a string and return it. The algorithm processes each character once, so the time complexity is O(n). The stack may store up to n characters in the worst case, giving O(n) space complexity.

This approach is intuitive and mirrors the problem statement directly. Many interviewers expect this solution first because the “remove the previous element” pattern naturally maps to a stack.

Approach 2: Two-Pointer In-Place Simulation (O(n) time, O(n) space)

You can simulate the stack using a write pointer over a character array. Convert the string into a mutable buffer and maintain an index that represents the current valid length. Iterate through the characters once. If the character is a letter, write it at the current pointer and move the pointer forward. If the character is a digit, move the pointer one position backward to delete the most recent letter.

This behaves exactly like push and pop operations on a stack, but uses pointer movement instead. The technique is common in two pointer style string processing and avoids explicit stack objects.

Each character is processed once, so the runtime remains O(n). The working buffer uses O(n) space, although the logic conceptually performs the simulation in-place.

Recommended for interviews: The stack-based solution is the most straightforward explanation and usually what interviewers expect first. It clearly shows that you recognized the “remove previous element” pattern common in string and stack problems. The two-pointer simulation demonstrates deeper understanding by replacing the stack with pointer manipulation while keeping the same O(n) performance.