3170. Lexicographically Minimum String After Removing Stars

UnknownView on LeetCode

String Stack Greedy Simulation

Time: O(n log n)

Space: O(n)

Problem Overview

Each * removes the nearest non-star character to its left.

Intuition

Each * removes the nearest non-star character to its left. Process left to right with a stack: push letters, pop on star. Same pattern as removing adjacent pairs but stars only delete to the left. Build result from stack contents.

Algorithm

1Stack<char> st.
2For each character c in s:
3If c is * and stack not empty: pop.
4Else if c is not *: push c.
5Return new string from stack (in order).

Example Walkthrough

Input: s = "leet**o*eet"

1.Push l,e,e,t. * pops t. * pops e. Continue until stars remove left neighbors.

Output: "leetoeet" (per problem examples)

Common Pitfalls

•Only remove when stack is non-empty — extra stars are ignored.
•Stars never get pushed onto the stack.
•Equivalent to LC 2390 Removing Stars From a String.

3170.cs

// Approach: Priority queue tracking (char, index); for each '*' remove lexicographically smallest char.
// Time: O(n log n) Space: O(n)

public class Solution
{
    public string ClearStars(string s)
    {
        // Create an array of Stacks to hold indices of each alphabet character
        Stack<int>[] characterIndices = new Stack<int>[26];
        // Initialize each Stack in the array
        for (int k = 0; k < 26; k++)
            characterIndices[k] = new Stack<int>();
        int length = s.Length;
        // Array to mark characters that should be removed
        bool[] remove = new bool[length];

        // Iterate over the characters in the string
        for (int i = 0; i < length; ++i)
        {
            if (s[i] == '*')
            {
                // Mark this star character for removal
                remove[i] = true;
                // Find the most recent character that is not a star and mark it for removal
                for (int j = 0; j < 26; ++j)
                {
                    if (characterIndices[j].Count > 0)
                    {
                        remove[characterIndices[j].Pop()] = true;
                        break; // Only remove one most recent character
                    }
                }
            }
            else // Push the index of this character onto the respective Stack
                characterIndices[s[i] - 'a'].Push(i);
        }

        // Construct the resulting string excluding the marked characters
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < length; ++i)
        {
            if (!remove[i])
                result.Append(s[i]);
        }

        return result.ToString();
    }
}

Was this solution helpful?