3170. Lexicographically Minimum String After Removing Stars
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 '*'
, 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 <= 105
s
consists only of lowercase English letters and'*'
.- The input is generated such that it is possible to delete all
'*'
characters.
Solutions
Solution 1: 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$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|