3170. Lexicographically Minimum String After Removing Stars

MediumStackGreedyHash TableStringHeap (Priority Queue)

Problem Description

You are given a string s. It may contain any number of '*' characters. Your task is to remove all '*' characters.

While there is a '*', perform 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.

Intuition

To solve this problem, we need to process each '*' in the string and find the smallest possible non-'*' character to remove each time. The smallest character is determined by lexicographical order, which is similar to alphabetical order.

The strategy is to use a data structure to keep track of indices of characters as we iterate through the string. For each '*', we determine the smallest non-'*' character that appears before it. If multiple candidates exist, we prefer the one appearing most recently to ensure the lexicographic order is maintained.

We utilize a dictionary g where each character maps to a list of its indices in the string. We also maintain a boolean array rem to mark characters and '*' for removal. As we iterate through the string:

If a '*' is encountered, mark it for removal in the rem array.
Check all characters from 'a' to 'z'. For the first character list (in lexicographical order) that is not empty, remove the last index it contains, marking this index for removal.
If a regular character is encountered, record its index.

Finally, create the result string by concatenating characters that are not marked for removal.

This ensures the remaining string is the lexicographically smallest possible after all operations are complete.

Learn more about Stack, Greedy and Heap (Priority Queue) patterns.

Solution Approach

The solution approach leverages two main data structures: a dictionary g to track indices of each character in the string s, and a boolean array rem to track which characters need to be deleted.

Here’s a step-by-step breakdown of the algorithm:

Initialize Data Structures:
- Create a dictionary g to store lists of indices for each character ('a' to 'z') as they appear in s.
- Initialize a boolean array rem of length n (where n is the length of the string) with False, indicating initially that no characters are marked for removal.
Traverse the String:
- For each character c in s with index i:
  - If c is '*', perform the following:
    - Mark rem[i] as True to indicate the '*' should be removed.
    - Iterate over each character a from 'a' to 'z'. For the first character for which g[a] is not empty, pop the last element (which is the largest index for that character due to how indices are appended) from g[a] and mark this index for removal by setting rem[index] to True.
  - If c is not '*', append the index i to the list g[c].
Build the Result String:
- Construct the result string by concatenating characters from s for which the corresponding index in rem is False (i.e., not marked for removal).

This method ensures that as we encounter '*', we remove the smallest lexicographical character preceding it, maintaining an optimally ordered resulting string.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the string s = "ab*cd*", and we wish to remove all the '*' characters following the described approach.

Step 1: Initialize Data Structures

g: A dictionary to map each character a-z to their indices in the string. Initially empty.
rem: A boolean array of length 6 (same as the length of s), initialized to [False, False, False, False, False, False].

Step 2: Traverse the String

Index 0: Character a, update g to {'a': [0], ...}.
Index 1: Character b, update g to {'a': [0], 'b': [1], ...}.
Index 2: Character *, mark rem as [False, False, True, False, False, False].
- Find the smallest character from g. 'a' and 'b' both have entries. Choose 'a' because it comes first lexicographically.
- Remove 'a' from g, resulting in g = {'a': [], 'b': [1], ...}.
- Mark the index of 'a' (0) for removal: rem becomes [True, False, True, False, False, False].
Index 3: Character c, update g to {'a': [], 'b': [1], 'c': [3], ...}.
Index 4: Character d, update g to {'a': [], 'b': [1], 'c': [3], 'd': [4], ...}.
Index 5: Character *, mark rem as [True, False, True, False, False, True].
- Find the smallest character from remaining entries in g. Here, 'b' is chosen as it is lexicographically smallest.
- Remove 'b' from g, resulting in g = {'a': [], 'b': [], 'c': [3], 'd': [4], ...}.
- Mark the index of 'b' (1) for removal: rem becomes [True, True, True, False, False, True].

Step 3: Build the Result String

Concatenate characters from s for indices that are not marked in rem. Indices 0, 1, 2, and 5 are marked for removal.
The resulting string is constructed from indices 3 and 4: "cd".

The lexicographically smallest resulting string after all operations is "cd".

Solution Implementation

1from collections import defaultdict
2from string import ascii_lowercase
3
4class Solution:
5    def clearStars(self, s: str) -> str:
6        # Dictionary to keep track of the indices of each alphabet character.
7        char_indices = defaultdict(list)
8        n = len(s)  # Length of the input string.
9        remove = [False] * n  # Boolean array to mark characters for removal.
10      
11        for i, char in enumerate(s):
12            if char == "*":
13                # Mark '*' for removal.
14                remove[i] = True
15                # Attempt to find the most recent alphabet character to remove.
16                for alphabet in ascii_lowercase:
17                    if char_indices[alphabet]:
18                        # Mark the most recent occurrence for removal and break loop.
19                        remove[char_indices[alphabet].pop()] = True
20                        break
21            else:
22                # Record the index of the current alphabet character.
23                char_indices[char].append(i)
24      
25        # Return the filtered string after removing marked characters.
26        return "".join(char for i, char in enumerate(s) if not remove[i])
27

1class Solution {
2    public String clearStars(String s) {
3        // Create an array of Deques to hold indices of each alphabet character
4        Deque<Integer>[] characterIndices = new Deque[26];
5        // Initialize each Deque in the array
6        Arrays.setAll(characterIndices, k -> new ArrayDeque<>());
7        int length = s.length();
8        // Array to mark characters that should be removed
9        boolean[] remove = new boolean[length];
10      
11        // Iterate over the characters in the string
12        for (int i = 0; i < length; ++i) {
13            if (s.charAt(i) == '*') {
14                // Mark this star character for removal
15                remove[i] = true;
16                // Find the most recent character that is not a star and mark it for removal
17                for (int j = 0; j < 26; ++j) {
18                    if (!characterIndices[j].isEmpty()) {
19                        remove[characterIndices[j].pop()] = true;
20                        break; // Only remove one most recent character
21                    }
22                }
23            } else {
24                // Push the index of this character onto the respective Deque
25                characterIndices[s.charAt(i) - 'a'].push(i);
26            }
27        }
28      
29        // Construct the resulting string excluding the marked characters
30        StringBuilder result = new StringBuilder();
31        for (int i = 0; i < length; ++i) {
32            if (!remove[i]) {
33                result.append(s.charAt(i));
34            }
35        }
36      
37        return result.toString();
38    }
39}
40

1#include <string>
2#include <stack>
3#include <vector>
4
5class Solution {
6public:
7    string clearStars(string s) {
8        std::stack<int> charStack[26];     // Use 26 stacks for each lowercase alphabet character.
9        int n = s.length();                // Length of the input string.
10        std::vector<bool> toRemove(n);     // Vector to indicate which characters to remove.
11
12        // Traverse the string and process each character.
13        for (int i = 0; i < n; ++i) {
14            if (s[i] == '*') {             // If the current character is '*', mark for removal.
15                toRemove[i] = true;
16                // Find the first non-empty stack and remove the character index from it.
17                for (int j = 0; j < 26; ++j) {
18                    if (!charStack[j].empty()) {
19                        toRemove[charStack[j].top()] = true; // Mark the character at the top of the stack for removal.
20                        charStack[j].pop(); // Remove the index from the stack.
21                        break;
22                    }
23                }
24            } else {
25                charStack[s[i] - 'a'].push(i); // Push the index of the character into the respective stack.
26            }
27        }
28
29        std::string result;
30        // Build the result string with characters that are not marked for removal.
31        for (int i = 0; i < n; ++i) {
32            if (!toRemove[i]) {
33                result.push_back(s[i]);
34            }
35        }
36        return result; // Return the final processed string.
37    }
38};
39

1function clearStars(s: string): string {
2    // Create an array of 26 empty arrays to store indices of each letter in the alphabet.
3    const indexGroups: number[][] = Array.from({ length: 26 }, () => []);
4    const length = s.length;
5    // Create an array to mark indices for removal.
6    const remove: boolean[] = Array(length).fill(false);
7  
8    // Iterate through each character in the string.
9    for (let i = 0; i < length; ++i) {
10        if (s[i] === '*') {
11            // Mark the '*' character for removal.
12            remove[i] = true;
13            // Attempt to remove the most recent character that is not a '*'.
14            for (let j = 0; j < 26; ++j) {
15                if (indexGroups[j].length) {
16                    // Pop the most recent index of the corresponding letter and mark it for removal.
17                    remove[indexGroups[j].pop()!] = true;
18                    break;
19                }
20            }
21        } else {
22            // Otherwise, record the index of the current character (non '*') in the corresponding group.
23            indexGroups[s.charCodeAt(i) - 97].push(i);
24        }
25    }
26
27    // Filter the string to remove all marked characters and return the cleaned string.
28    return s
29        .split('')
30        .filter((_, i) => !remove[i])
31        .join('');
32}
33

Time and Space Complexity

The time complexity of the code is O(n * |Σ|), where n is the length of the string s, and |Σ| (Sigma) is the size of the character set, which is 26 in this problem. This comes from the outer loop iterating through each character of the string, and the inner loop iterating over the fixed character set (ascii_lowercase), resulting in O(n * 26) simplifiable to O(n) in practice due to the constant factor.

The space complexity is O(n). This arises from the use of rem and g. The list rem has n elements corresponding to each character of the string. The defaultdict g holds indices for each character that appears in the string, but its total length across all keys doesn't exceed n, since it stores indices for each non-star character.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: