Clear Digits solution and explanation
Google
9 more videos on this problem
Clear Digits - Leetcode 3174 - PythonNeetCodeIO · 7:42 · 7K views
Clear Digits | 4 Detailed Approaches | Leetcode 3174 | codestorywithMIKcodestorywithMIK · 28:31 · 4K views
3174. Clear Digits | Simulation | Arrays | 2 PointersAryan Mittal · 5:09 · 4K views
Clear Digits | Leetcode 3174Techdose · 4:11 · 3K views
Clear Digits | Leetcode 3174Ayushi Sharma · 7:44 · 2K views
3174. Clear Digits | leetcode daily challenge | shashcode | java | dsa | shashwatShashCode · 9:07 · 1K views
Leetcode | 3174. Clear Digits | Easy | Java SolutionDeveloper Docs · 3:32 · 1K views
3174. Clear Digits | Leetcode Daily ChallengeEthos Typos · 5:52 · 479 views
LeetCode 3174 Clear Digits | Easy | Stack | Simulation | Asked in GoogleCode Harmony · 14:47 · 239 views
3174. Clear Digits (Leetcode Easy)Programming Live with Larry · 3:00 · 181 views
The 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.
Example 1:
Input: s = "abc"
Output: "abc"
Explanation:
There is no digit in the string.
Example 2:
Input: s = "cb34"
Output: ""
Explanation:
First, we apply the operation on s[2], and s becomes "c4".
Then we apply the operation on s[1], and s becomes "".
Constraints:
1 <= s.length <= 100sconsists only of lowercase English letters and digits.- The input is generated such that it is possible to delete all digits.
Approach overview
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.
Approach 1: Stack-Based Approach
This approach uses a stack data structure to solve the problem. A stack helps us easily keep track of and remove characters because of its LIFO (Last In, First Out) behavior. Here's the detailed plan:
- Iterate through each character in the string.
- If the character is a non-digit, push it onto the stack.
- If it's a digit, pop a character from the stack (which would be the closest non-digit to its left).
- Continue this until you have traversed the entire string.
At the end, the stack contains the result after all digits have been removed following the given rule.
def clear_digits(s: str) -> str:
stack = []
for char in s:
if char.isdigit():
if stack:
stack.pop()
else:
stack.append(char)
return ''.join(stack)
s = 'cb34'
print(clear_digits(s))import java.util.Stack;
public class ClearDigits {
public static String clearDigits(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
if (!stack.isEmpty()) {
stack.pop();
}
} else {
stack.push(c);
}
}
StringBuilder result = new StringBuilder();
for (char c : stack) {
result.append(c);
}
return result.toString();
}
public static void main(String[] args) {
String s = "cb34";
System.out.println(clearDigits(s));
}
}#include <iostream>
#include <stack>
#include <cctype>
std::string clearDigits(const std::string &s) {
std::stack<char> st;
for (char c : s) {
if (std::isdigit(c)) {
if (!st.empty()) {
st.pop();
}
} else {
st.push(c);
}
}
std::string result = "";
while (!st.empty()) {
result = st.top() + result; // Prepend to the result
st.pop();
}
return result;
}
int main() {
std::string s = "cb34";
std::cout << clearDigits(s) << std::endl;
return 0;
}function clearDigits(s) {
const stack = [];
for (let i = 0; i < s.length; ++i) {
if (/[0-9]/.test(s[i])) {
if (stack.length > 0) {
stack.pop();
}
} else {
stack.push(s[i]);
}
}
return stack.join('');
}
const s = 'cb34';
console.log(clearDigits(s));#include <stdio.h>
#include <string.h>
#include <ctype.h>
void clearDigits(char *s) {
char stack[100];
int top = -1;
for (int i = 0; s[i] != '\0'; ++i) {
if (isdigit(s[i])) {
if (top != -1) {
--top; // pop the non-digit character
}
} else {
stack[++top] = s[i];
}
}
stack[++top] = '\0';
printf("%s\n", stack);
}
int main() {
char s[] = "cb34";
clearDigits(s);
return 0;
}using System;
using System.Collections.Generic;
public class ClearDigitsSolution {
public static string ClearDigits(string s) {
Stack<char> stack = new Stack<char>();
foreach (char c in s) {
if (Char.IsDigit(c)) {
if (stack.Count > 0) {
stack.Pop();
}
} else {
stack.Push(c);
}
}
char[] result = stack.ToArray();
Array.Reverse(result);
return new string(result);
}
public static void Main() {
string s = "cb34";
Console.WriteLine(ClearDigits(s));
}
}This Python implementation utilizes a list as a stack. It iterates through each character, appending non-digits to the stack and removing the top element for each digit. The result string is built by joining the characters left in the stack.
Time Complexity: O(n), due to iterating through each character.
Space Complexity: O(n), required for storing characters in the stack.
Approach 2: Two-Pointer Approach
This approach utilizes two pointers to effectively manage the character positions during the removal process without using a stack. It provides an intuitive way to keep track of characters to be removed as we traverse the string:
- Use the first pointer to iterate over each character in the array.
- Utilize a second pointer (to non-digits) to move only for non-digit characters.
- If a digit is found, reduce the non-digit pointer by one to 'remove' the closest non-digit character.
- Finally, reconstruct the string using characters that remain between the two pointers.
def clear_digits(s: str) -> str:
chars = list(s)
j = 0
for i in range(len(chars)):
if chars[i].isdigit():
if j > 0:
j -= 1
else:
chars[j] = chars[i]
j += 1
return ''.join(chars[:j])
s = 'cb34'
print(clear_digits(s))public class ClearDigits {
public static String clearDigits(String s) {
int j = 0;
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (Character.isDigit(chars[i])) {
if (j > 0) {
--j;
}
} else {
chars[j++] = chars[i];
}
}
return new String(chars, 0, j);
}
public static void main(String[] args) {
String s = "cb34";
System.out.println(clearDigits(s));
}
}#include <iostream>
#include <cctype>
std::string clearDigits(std::string s) {
int j = 0;
for (int i = 0; i < s.size(); ++i) {
if (isdigit(s[i])) {
if (j > 0) {
--j; // effectively 'erase' one non-digit character
}
} else {
s[j++] = s[i]; // re-assign non-digit character
}
}
return s.substr(0, j);
}
int main() {
std::string s = "cb34";
std::cout << clearDigits(s) << std::endl;
return 0;
}function clearDigits(s) {
const chars = s.split('');
let j = 0;
for (let i = 0; i < chars.length; ++i) {
if (/[0-9]/.test(chars[i])) {
if (j > 0) {
j -= 1; // step back to 'erase' a character
}
} else {
chars[j++] = chars[i];
}
}
return chars.slice(0, j).join('');
}
const s = 'cb34';
console.log(clearDigits(s));#include <stdio.h>
#include <string.h>
#include <ctype.h>
void clearDigits(char *s) {
int j = 0;
for (int i = 0; s[i] != '\0'; ++i) {
if (isdigit(s[i])) {
if (j > 0) {
--j; // move back one position to 'erase' the non-digit character
}
} else {
s[j++] = s[i]; // move the non-digit character to the left
}
}
s[j] = '\0'; // null-terminate new string
printf("%s\n", s);
}
int main() {
char s[] = "cb34";
clearDigits(s);
return 0;
}using System;
public class ClearDigitsSolution {
public static string ClearDigits(string s) {
char[] chars = s.ToCharArray();
int j = 0;
for (int i = 0; i < chars.Length; i++) {
if (Char.IsDigit(chars[i])) {
if (j > 0)
j--;
} else {
chars[j++] = chars[i];
}
}
return new string(chars, 0, j);
}
public static void Main() {
string s = "cb34";
Console.WriteLine(ClearDigits(s));
}
}The Python solution directly modifies a list of characters derived from the string, adjusting in-place with two pointers: one for reading and one to edit the final resultant position. Finally, the list from 0 to the edited length is transformed back into a string.
Time Complexity: O(n), reflecting direct traversal and manipulation of the list.
Space Complexity: O(1), aside from the input's intrinsic space.
Approach 3: Stack + Simulation
We use a stack stk to simulate this process. We traverse the string s. If the current character is a digit, we pop the top element from the stack. Otherwise, we push the current character into the stack.
Finally, we concatenate the elements in the stack into a string and return it.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s.
function clearDigits(s: string): string {
const stk: string[] = [];
for (const c of s) {
if (!isNaN(parseInt(c))) {
stk.pop();
} else {
stk.push(c);
}
}
return stk.join('');
}func clearDigits(s string) string {
stk := []byte{}
for i := range s {
if s[i] >= '0' && s[i] <= '9' {
stk = stk[:len(stk)-1]
} else {
stk = append(stk, s[i])
}
}
return string(stk)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Stack-Based Approach | Time Complexity: O(n), due to iterating through each character. Space Complexity: O(n), required for storing characters in the stack. |
| Two-Pointer Approach | Time Complexity: O(n), reflecting direct traversal and manipulation of the list. Space Complexity: O(1), aside from the input's intrinsic space. |
| Stack + Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Simulation | O(n) | O(n) | Best general solution. Easy to reason about when removing the most recent character. |
| Two-Pointer Simulation | O(n) | O(n) | When you want stack behavior using pointer manipulation or in-place style string processing. |
Frequently asked questions
Is Clear Digits easy or hard?
Clear Digits is classified as an Easy problem on LeetCode with a high acceptance rate. The challenge mainly tests whether you recognize the stack pattern used to remove the most recent character when processing a string.
Clear Digits Python/Java solution
Python and Java implementations typically use a list or stack-like structure. Iterate through the string, append letters, and pop the last element when a digit appears. This approach keeps the runtime O(n) and the implementation concise.
How to solve Clear Digits in O(n)?
Scan the string from left to right while maintaining a stack or simulated stack. Push letters onto the structure and remove the most recent letter whenever a digit appears. Because every character triggers at most one push or pop, the entire process runs in O(n) time.
What is the best approach for Clear Digits?
The stack-based simulation is the most common solution. Traverse the string, push letters onto a stack, and pop one letter whenever a digit appears. This directly models the rule that a digit removes the closest character to its left. The algorithm runs in O(n) time and O(n) space.
Is Clear Digits asked at Google/Amazon/Meta?
Clear Digits follows a classic stack simulation pattern frequently used in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, similar questions about removing previous elements or processing strings with stack logic appear often.
What data structure is used in Clear Digits?
A stack is the primary data structure used to solve Clear Digits efficiently. It allows constant-time removal of the most recent character, which matches the rule that each digit deletes the closest letter to its left.
What is the time complexity of Clear Digits?
The optimal time complexity is O(n), where n is the length of the string. Each character is processed exactly once. Stack push and pop operations are constant time, so the overall algorithm remains linear.