3039. Apply Operations to Make String Empty
Description
You are given a string s
.
Consider performing the following operation until s
becomes empty:
- For every alphabet character from
'a'
to'z'
, remove the first occurrence of that character ins
(if it exists).
For example, let initially s = "aabcbbca"
. We do the following operations:
- Remove the underlined characters
s = "aabcbbca"
. The resulting string iss = "abbca"
. - Remove the underlined characters
s = "abbca"
. The resulting string iss = "ba"
. - Remove the underlined characters
s = "ba"
. The resulting string iss = ""
.
Return the value of the string s
right before applying the last operation. In the example above, answer is "ba"
.
Example 1:
Input: s = "aabcbbca" Output: "ba" Explanation: Explained in the statement.
Example 2:
Input: s = "abcd" Output: "abcd" Explanation: We do the following operation: - Remove the underlined characters s = "abcd". The resulting string is s = "". The string just before the last operation is "abcd".
Constraints:
1 <= s.length <= 5 * 105
s
consists only of lowercase English letters.
Solutions
Solution 1: Hash Table or Array
We use a hash table or array $cnt$ to record the occurrence times of each character in string $s$, and use another hash table or array $last$ to record the last occurrence position of each character in string $s$. The maximum occurrence times of characters in string $s$ is denoted as $mx$.
Then we traverse the string $s$. If the occurrence times of the current character equals $mx$ and the position of the current character equals the last occurrence position of this character, then we add the current character to the answer.
After the traversal, we return the answer.
The time complexity is $O(n)$, and the space complexity is $O(|\Sigma|)$, where $n$ is the length of string $s$, and $\Sigma$ is the character set. In this problem, $\Sigma$ is the set of lowercase English letters.
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|