Lexicographically Minimum String After Removing Stars solution and explanation
Google
9 more videos on this problem
Lexicographically Minimum String After Removing Stars | Easy | Leetcode 3170 | codestorywithMIKcodestorywithMIK · 23:42 · 11K views
Lexicographically Minimum String After Removing Stars | Leetcode 3170Techdose · 9:54 · 3K views
3170. Lexicographically Minimum String After Removing Stars | 2 Approaches | Greedy | Min HeapAryan Mittal · 16:15 · 2K views
Daily Leetcode #1894: Jun 07, 2025 - 3170. Lexicographically Minimum String After Removing StarsProgramming Live with Larry · 9:41 · 519 views
3170. Lexicographically Minimum String After Removing Stars | Weekly Leetcode 400codingMohan · 13:17 · 496 views
3170. Lexicographically Minimum String After Removing Stars | Leetcode Daily - PythonLeetcode Daily · 5:28 · 375 views
3170. Lexicographically Minimum String After Removing Stars | HashMap | Min Heap | LeetcodeRapid Syntax · 16:09 · 361 views
3170. Lexicographically Minimum String After Removing Stars leetcode solutionsUnfiltered Programmer · 10:59 · 324 views
3170. Lexicographically Minimum String After Removing Stars (Leetcode Medium)Programming Live with Larry · 11:56 · 307 views
LeetCode 3170 - Lexicographically Minimum String After Removing Stars - JavaAlpha-Code · 13:40 · 278 views
The problem
You are given a string s. It may contain any number of '*' characters. Your task is to remove all '*' characters.
While there is a '*', do the following operation:
- Delete the leftmost
'*'and the smallest non-'*'character to its left. If there are several smallest characters, you can delete any of them.
Return the lexicographically smallest resulting string after removing all '*' characters.
Example 1:
Input: s = "aaba*"
Output: "aab"
Explanation:
We should delete one of the 'a' characters with '*'. If we choose s[3], s becomes the lexicographically smallest.
Example 2:
Input: s = "abc"
Output: "abc"
Explanation:
There is no '*' in the string.
Constraints:
1 <= s.length <= 105sconsists only of lowercase English letters and'*'.- The input is generated such that it is possible to delete all
'*'characters.
Approach overview
Problem Overview: You receive a string containing lowercase letters and *. Each star deletes itself and one character to its left. When multiple characters exist to the left, remove the lexicographically smallest one so the final string becomes as small as possible.
Approach 1: Stack to Track Before Deletions (O(n log n) time, O(n) space)
Scan the string from left to right while tracking characters that appear before each *. Maintain a stack (or indexed storage) of characters along with their positions, and use a min‑heap or ordered structure to quickly locate the smallest available character. When you encounter a star, pop the lexicographically smallest character that appears before it and mark both the star and that character for deletion. Continue scanning until the end, then rebuild the string using only characters not removed. The key idea is greedy removal: deleting the smallest possible character before every star guarantees the remaining prefix stays lexicographically minimal. This technique commonly combines stack tracking with a heap (priority queue) to efficiently select the best character to delete.
Approach 2: Two Pointers Technique (O(n) time, O(n) space)
A more optimized method processes the string while maintaining candidate positions for each character. Instead of repeatedly searching, track indices of characters using fixed buckets (for example, 26 lists for each letter). Move through the string with a pointer and record the positions of characters you see. When a * appears, identify the smallest available letter bucket that still has a valid index and remove the most recent occurrence of that letter. This effectively simulates deletions without expensive heap operations. After processing the entire string, reconstruct the result by skipping removed indices. Because each character is inserted and removed at most once, the algorithm runs in linear time. The logic relies on greedy selection and efficient character tracking, a common pattern in string and greedy problems.
Recommended for interviews: The linear two‑pointer/bucket strategy is usually what interviewers expect. It demonstrates that you understand the greedy requirement and can optimize away repeated searches. Starting with the stack + heap idea is still valuable because it clearly models the rule "remove the smallest character before each star" and shows the reasoning before optimizing to O(n).
Approach 1: Using Stack to Track Before Deletions
This approach utilizes a stack data structure to keep track of characters in the string. As we iterate through the string, we push non-'*' characters onto the stack. When we encounter a '*', we pop from the stack, effectively removing the smallest character before the '*'. The stack allows us to maintain the remaining string in a way that can efficiently remove and process characters in a LIFO manner. Finally, we assemble our result from the characters remaining in the stack, which ensures the string is the lexicographically smallest possible after all required deletions.
def remove_stars(s):
stack = []
for char in s:
if char == '*':
if stack:
stack.pop()
else:
stack.append(char)
return ''.join(stack)
s = "aaba*"
result = remove_stars(s)
print(result)import java.util.Stack;
public class RemoveStars {
public static String removeStars(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (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 = "aaba*";
System.out.println(removeStars(s));
}
}#include <iostream>
#include <stack>
std::string removeStars(const std::string &s) {
std::stack<char> stack;
for (char c : s) {
if (c == '*') {
if (!stack.empty()) stack.pop();
} else {
stack.push(c);
}
}
std::string result;
while (!stack.empty()) {
result = stack.top() + result;
stack.pop();
}
return result;
}
int main() {
std::string s = "aaba*";
std::cout << removeStars(s) << std::endl;
return 0;
}function removeStars(s) {
let stack = [];
for (let char of s) {
if (char === '*') {
if (stack.length > 0) stack.pop();
} else {
stack.push(char);
}
}
return stack.join('');
}
const s = "aaba*";
console.log(removeStars(s));#include <stdio.h>
#include <string.h>
char* removeStars(char* s) {
int len = strlen(s);
char* stack = (char*)malloc(len + 1);
int index = 0;
for (int i = 0; i < len; i++) {
if (s[i] == '*') {
if (index > 0) index--;
} else {
stack[index++] = s[i];
}
}
stack[index] = '\0';
return stack;
}
int main() {
char str[] = "aaba*";
char* result = removeStars(str);
printf("%s\n", result);
free(result);
return 0;
}using System;
using System.Collections.Generic;
public class Program {
public static string RemoveStars(string s) {
Stack<char> stack = new Stack<char>();
foreach (char c in s) {
if (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 = "aaba*";
Console.WriteLine(RemoveStars(s));
}
}In this Python solution, a list is used as a stack to append characters from the string. We pop from the stack if a '*' character is encountered, resulting in an efficient lexicographical reduction.
Time Complexity: O(n) for linear traversal.
Space Complexity: O(n), corresponding to the list size accounting for deletions.
Approach 2: Two Pointers Technique
This approach leverages two pointers: one pointing to the current position in the input and another building the result in place. The fundamental idea is to overwrite the unnecessary characters in the array as we build the result string. We use the second pointer to track the last added character when we encounter a '*' and need to delete. After iterating through the entire input, the section of the array up to the second pointer will hold the resulting string.
def remove_stars(s):
chars = list(s)
j = 0
for i in range(len(chars)):
if chars[i] == '*':
if j > 0:
j -= 1
else:
chars[j] = chars[i]
j += 1
return ''.join(chars[:j])
s = "aaba*"
result = remove_stars(s)
print(result)public class RemoveStarsInPlace {
public static String removeStars(String s) {
char[] charArray = s.toCharArray();
int j = 0;
for (int i = 0; i < charArray.length; i++) {
if (charArray[i] == '*') {
if (j > 0) j--;
} else {
charArray[j++] = charArray[i];
}
}
return new String(charArray, 0, j);
}
public static void main(String[] args) {
String s = "aaba*";
System.out.println(removeStars(s));
}
}#include <iostream>
using namespace std;
string removeStars(string s) {
int j = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '*') {
if (j > 0) j--;
} else {
s[j++] = s[i];
}
}
return s.substr(0, j);
}
int main() {
string s = "aaba*";
cout << removeStars(s) << endl;
return 0;
}function removeStars(s) {
let chars = s.split('');
let j = 0;
for (let i = 0; i < chars.length; i++) {
if (chars[i] === '*') {
if (j > 0) j--;
} else {
chars[j++] = chars[i];
}
}
return chars.slice(0, j).join('');
}
const s = "aaba*";
console.log(removeStars(s));#include <stdio.h>
#include <string.h>
char* removeStars(char* s) {
int len = strlen(s);
int j = 0;
for (int i = 0; i < len; i++) {
if (s[i] == '*') {
if (j > 0) j--;
} else {
s[j++] = s[i];
}
}
s[j] = '\0';
return s;
}
int main() {
char str[] = "aaba*";
printf("%s\n", removeStars(str));
return 0;
}using System;
public class Program {
public static string RemoveStars(string s) {
char[] arr = s.ToCharArray();
int j = 0;
for (int i = 0; i < arr.Length; i++) {
if (arr[i] == '*') {
if (j > 0) j--;
} else {
arr[j++] = arr[i];
}
}
return new String(arr, 0, j);
}
public static void Main() {
string s = "aaba*";
Console.WriteLine(RemoveStars(s));
}
}The Python solution modifies the list in place using a two-pointer strategy. The list is converted back to a string after constructing the desired output up to pointer j.
Time Complexity: O(n)
Space Complexity: O(n) considering immutable strings in Python but in-place list logic.
Approach 3: Record Indices by Character
We define an array g to record the index list of each character, and a boolean array rem of length n to record whether each character needs to be deleted.
We traverse the string s:
If the current character is an asterisk, we need to delete it, so we mark rem[i] as deleted. At the same time, we need to delete the character with the smallest lexicographical order and the largest index at this time. We traverse the 26 lowercase letters in ascending order. If g[a] is not empty, we delete the last index in g[a] and set the corresponding index in rem as deleted.
If the current character is not an asterisk, we add the index of the current character to g.
Finally, we traverse s and concatenate the undeleted characters.
The time complexity is O(n times |\Sigma|), and the space complexity is O(n). Where n is the length of the string s, and |\Sigma| is the size of the character set. In this problem, |\Sigma| = 26.
function clearStars(s: string): string {
const g: number[][] = Array.from({ length: 26 }, () => []);
const n = s.length;
const rem: boolean[] = Array(n).fill(false);
for (let i = 0; i < n; ++i) {
if (s[i] === '*') {
rem[i] = true;
for (let j = 0; j < 26; ++j) {
if (g[j].length) {
rem[g[j].pop()!] = true;
break;
}
}
} else {
g[s.charCodeAt(i) - 97].push(i);
}
}
return s
.split('')
.filter((_, i) => !rem[i])
.join('');
}func clearStars(s string) string {
g := make([][]int, 26)
n := len(s)
rem := make([]bool, n)
for i, c := range s {
if c == '*' {
rem[i] = true
for j := 0; j < 26; j++ {
if len(g[j]) > 0 {
rem[g[j][len(g[j])-1]] = true
g[j] = g[j][:len(g[j])-1]
break
}
}
} else {
g[c-'a'] = append(g[c-'a'], i)
}
}
ans := []byte{}
for i := range s {
if !rem[i] {
ans = append(ans, s[i])
}
}
return string(ans)
}impl Solution {
pub fn clear_stars(s: String) -> String {
let n = s.len();
let s_bytes = s.as_bytes();
let mut g: Vec<Vec<usize>> = vec![vec![]; 26];
let mut rem = vec![false; n];
let chars: Vec<char> = s.chars().collect();
for (i, &ch) in chars.iter().enumerate() {
if ch == '*' {
rem[i] = true;
for j in 0..26 {
if let Some(idx) = g[j].pop() {
rem[idx] = true;
break;
}
}
} else {
g[(ch as u8 - b'a') as usize].push(i);
}
}
chars
.into_iter()
.enumerate()
.filter_map(|(i, ch)| if !rem[i] { Some(ch) } else { None })
.collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Stack to Track Before Deletions | Time Complexity: O(n) for linear traversal. |
| Two Pointers Technique | Time Complexity: O(n) |
| Record Indices by Character | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack + Priority Queue | O(n log n) | O(n) | Straightforward greedy simulation when you want a clear mapping between stars and removed characters |
| Two Pointers / Character Buckets | O(n) | O(n) | Optimal solution for interviews and large inputs; avoids heap operations |
Frequently asked questions
Is Lexicographically Minimum String After Removing Stars easy or hard?
The problem is rated Medium on LeetCode. The difficulty comes from combining greedy choice with efficient tracking of the smallest available character. A naive simulation is simple, but optimizing it to O(n) requires careful use of stacks or indexed buckets.
Lexicographically Minimum String After Removing Stars Python/Java solution
In Python or Java, maintain lists or stacks storing indices of characters. When a '*' appears, remove the smallest available character index and mark it as deleted. After the scan, rebuild the string using characters whose indices were not removed. The optimized implementation runs in O(n) time.
How to solve Lexicographically Minimum String After Removing Stars in O(n)?
Traverse the string while storing indices of characters in 26 buckets (one for each letter). When you encounter '*', locate the smallest bucket that still contains an index and remove the most recent occurrence of that character. Mark both the star and the removed character, then reconstruct the final string. Since each index is handled once, the overall complexity stays O(n).
What is the best approach for Lexicographically Minimum String After Removing Stars?
The optimal approach uses a greedy strategy with indexed character tracking (often implemented with 26 buckets or stacks). Each time a '*' appears, remove the smallest lexicographic character that exists to its left. Because every character is processed and removed at most once, this approach runs in O(n) time with O(n) space.
Is Lexicographically Minimum String After Removing Stars asked at Google/Amazon/Meta?
Problems combining greedy logic with stacks, heaps, or string manipulation are common in interviews at companies like Amazon, Google, and Meta. Variants of this problem test your ability to maintain ordering constraints while processing deletions efficiently.
What data structure is used in Lexicographically Minimum String After Removing Stars?
Typical solutions use stacks to track characters before a star and either a min‑heap or fixed character buckets to quickly find the smallest letter. These structures support efficient deletions while scanning the string from left to right.
What is the time complexity of Lexicographically Minimum String After Removing Stars?
The optimized greedy solution runs in O(n) time and O(n) space, where n is the length of the string. Each character is inserted once and removed at most once. A simpler implementation using a priority queue takes O(n log n) time because every deletion requires a heap operation.