Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
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:
'*' 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 <= 105s consists only of lowercase English letters and '*'.'*' characters.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Stack · Greedy
"aaba*"
"abc"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3170: Lexicographically Minimum String After Removing Stars
class Solution {
public String clearStars(String s) {
Deque<Integer>[] g = new Deque[26];
Arrays.setAll(g, k -> new ArrayDeque<>());
int n = s.length();
boolean[] rem = new boolean[n];
for (int i = 0; i < n; ++i) {
if (s.charAt(i) == '*') {
rem[i] = true;
for (int j = 0; j < 26; ++j) {
if (!g[j].isEmpty()) {
rem[g[j].pop()] = true;
break;
}
}
} else {
g[s.charAt(i) - 'a'].push(i);
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; ++i) {
if (!rem[i]) {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
// Accepted solution for LeetCode #3170: Lexicographically Minimum String After Removing Stars
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)
}
# Accepted solution for LeetCode #3170: Lexicographically Minimum String After Removing Stars
class Solution:
def clearStars(self, s: str) -> str:
g = defaultdict(list)
n = len(s)
rem = [False] * n
for i, c in enumerate(s):
if c == "*":
rem[i] = True
for a in ascii_lowercase:
if g[a]:
rem[g[a].pop()] = True
break
else:
g[c].append(i)
return "".join(c for i, c in enumerate(s) if not rem[i])
// Accepted solution for LeetCode #3170: Lexicographically Minimum String After Removing Stars
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()
}
}
// Accepted solution for LeetCode #3170: Lexicographically Minimum String After Removing Stars
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('');
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan left (or right) to find the next greater/smaller element. The inner scan can visit up to n elements per outer iteration, giving O(n²) total comparisons. No extra space needed beyond loop variables.
Each element is pushed onto the stack at most once and popped at most once, giving 2n total operations = O(n). The stack itself holds at most n elements in the worst case. The key insight: amortized O(1) per element despite the inner while-loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.