Lexicographically Minimum String After Removing Stars

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.

Examples

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 <= 10^5
• s consists only of lowercase English letters and '*'.
• The input is generated such that it is possible to delete all '*' characters.

Solution

Method 1 – Using Greedy approach

Each time we see a * in the string, we must remove the lexicographically smallest non-star character to its left. To do this, we use a min-heap to track each non-star character and its index. When a * is found, we mark the smallest such character (by index) for deletion in a map. Finally, we build the result string by skipping all characters marked for deletion and all * characters.

Code

C++

class Solution {
public:
    string clearStars(string s) {
        int n = s.size();
        vector<stack<int>> posStack(26);
        vector<char> arr(s.begin(), s.end());
        for (int i = 0; i < n; ++i) {
            if (arr[i] != '*') {
                posStack[arr[i] - 'a'].push(i);
            } else {
                for (int j = 0; j < 26; ++j) {
                    if (!posStack[j].empty()) {
                        arr[posStack[j].top()] = '*';
                        posStack[j].pop();
                        break;
                    }
                }
            }
        }
        string ans;
        for (char c : arr) {
            if (c != '*') ans += c;
        }
        return ans;
    }
};

Go

func clearStars(s string) string {
    n := len(s)
    posStack := make([][]int, 26)
    arr := []byte(s)
    for i := 0; i < n; i++ {
        if arr[i] != '*' {
            idx := arr[i] - 'a'
            posStack[idx] = append(posStack[idx], i)
        } else {
            for j := 0; j < 26; j++ {
                if len(posStack[j]) > 0 {
                    last := len(posStack[j]) - 1
                    arr[posStack[j][last]] = '*'
                    posStack[j] = posStack[j][:last]
                    break
                }
            }
        }
    }
    ans := make([]byte, 0, n)
    for _, c := range arr {
        if c != '*' {
            ans = append(ans, c)
        }
    }
    return string(ans)
}

Java

import java.util.*;

class Solution {
    public String clearStars(String s) {
        Deque<Integer>[] posStack = new Deque[26];
        for (int i = 0; i < 26; i++) {
            posStack[i] = new ArrayDeque<>();
        }
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != '*') {
                posStack[arr[i] - 'a'].push(i);
            } else {
                for (int j = 0; j < 26; j++) {
                    if (!posStack[j].isEmpty()) {
                        arr[posStack[j].pop()] = '*';
                        break;
                    }
                }
            }
        }

        StringBuilder ans = new StringBuilder();
        for (char c : arr) {
            if (c != '*') {
                ans.append(c);
            }
        }
        return ans.toString();
    }
}

Kotlin

class Solution {
    fun clearStars(s: String): String {
        val n = s.length
        val posStack = Array(26) { ArrayDeque<Int>() }
        val arr = s.toCharArray()
        for (i in 0 until n) {
            if (arr[i] != '*') {
                posStack[arr[i] - 'a'].addFirst(i)
            } else {
                for (j in 0 until 26) {
                    if (posStack[j].isNotEmpty()) {
                        arr[posStack[j].removeFirst()] = '*'
                        break
                    }
                }
            }
        }
        val ans = StringBuilder()
        for (c in arr) {
            if (c != '*') ans.append(c)
        }
        return ans.toString()
    }
}

Python

class Solution:
    def clearStars(self, s: str) -> str:
        n = len(s)
        pos_stack = [[] for _ in range(26)]
        arr = list(s)
        for i, c in enumerate(arr):
            if c != '*':
                pos_stack[ord(c) - ord('a')].append(i)
            else:
                for j in range(26):
                    if pos_stack[j]:
                        arr[pos_stack[j].pop()] = '*'
                        break
        ans = [c for c in arr if c != '*']
        return ''.join(ans)

Rust

impl Solution {
    pub fn clear_stars(s: String) -> String {
        let n = s.len();
        let mut pos_stack: Vec<Vec<usize>> = vec![Vec::new(); 26];
        let mut arr: Vec<char> = s.chars().collect();
        for i in 0..n {
            if arr[i] != '*' {
                pos_stack[(arr[i] as u8 - b'a') as usize].push(i);
            } else {
                for j in 0..26 {
                    if let Some(idx) = pos_stack[j].pop() {
                        arr[idx] = '*';
                        break;
                    }
                }
            }
        }
        arr.into_iter().filter(|&c| c != '*').collect()
    }
}

Complexity

• ⏰ Time complexity: - O(n * 26) = O(n). For each character in the string, we may check up to 26 stacks (one for each lowercase letter) when processing a *. Since 26 is a constant, this is effectively O(n).
• 🧺 Space complexity: O(n). We use up to 26 stacks to store indices, and an array to store the modified string, both of which require O(n) space in the worst case.