进行操作使字符串为空

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 in s (if it exists).

For example, let initially s = "aabcbbca". We do the following operations:

• Remove the underlined characters s = "aabcbbca". The resulting string is s = "abbca".
• Remove the underlined characters s = "abbca". The resulting string is s = "ba".
• Remove the underlined characters s = "ba". The resulting string is s = "".

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.

/*
 * 思路：
 * 1. 使用 Java Stream API 处理字符串，遍历字母 'a' 到 'z'。
 * 2. 每次找到并删除最早出现的字符。
 * 3. 使用一个 List 保存每次操作前的字符串。
 */

import java.util.*;
import java.util.stream.IntStream;

public class StreamSolution {
    public String findLastBeforeEmpty(String s) {
        List<String> history = new ArrayList<>();
        history.add(s);
        for (char c = 'a'; c <= 'z'; c++) {
            int index = IntStream.range(0, s.length()).filter(i -> s.charAt(i) == c).findFirst().orElse(-1);
            if (index != -1) {
                s = s.substring(0, index) + s.substring(index + 1);
                history.add(s);
            }
        }
        return history.size() > 1 ? history.get(history.size() - 2) : s;
    }
}

这个题解似乎并不完全符合题目的要求。题目要求移除字符串中按字母表顺序出现的最早字符，直到字符串为空。但题解中的方法更像是查找并返回出现最多次的字符的最后出现位置的字符串。具体步骤如下： 1. 使用Counter计算每个字符在字符串中出现的次数。 2. 构建一个字典记录每个字符最后一次出现的位置。 3. 找到出现次数最多的字符，记录这些字符最后一次出现的索引。 4. 按索引顺序返回这些字符组成的字符串。

O(n + k log k)

O(1)