将字符串中的元音字母排序

Given a 0-indexed string s, permute s to get a new string t such that:

• All consonants remain in their original places. More formally, if there is an index i with 0 <= i < s.length such that s[i] is a consonant, then t[i] = s[i].
• The vowels must be sorted in the nondecreasing order of their ASCII values. More formally, for pairs of indices i, j with 0 <= i < j < s.length such that s[i] and s[j] are vowels, then t[i] must not have a higher ASCII value than t[j].

Return the resulting string.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in lowercase or uppercase. Consonants comprise all letters that are not vowels.

 

Example 1:

Input: s = "lEetcOde"
Output: "lEOtcede"
Explanation: 'E', 'O', and 'e' are the vowels in s; 'l', 't', 'c', and 'd' are all consonants. The vowels are sorted according to their ASCII values, and the consonants remain in the same places.

Example 2:

Input: s = "lYmpH"
Output: "lYmpH"
Explanation: There are no vowels in s (all characters in s are consonants), so we return "lYmpH".

 

Constraints:

• 1 <= s.length <= 105
• s consists only of letters of the English alphabet in uppercase and lowercase.

/*
题目思路：
1. 使用流操作提取和排序元音字母。
2. 使用列表保存元音字母的位置。
3. 构建新的字符串，将排序后的元音字母放在相应的位置。
*/

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

public class Solution {
    public String rearrangeVowels(String s) {
        String vowels = "aeiouAEIOU";
        List<Character> sortedVowels = s.chars()
                .filter(c -> vowels.indexOf(c) != -1)
                .mapToObj(c -> (char) c)
                .sorted()
                .collect(Collectors.toList());

        Iterator<Character> vowelIterator = sortedVowels.iterator();

        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (vowels.indexOf(c) != -1) {
                result.append(vowelIterator.next());
            } else {
                result.append(c);
            }
        }

        return result.toString();
    }
}

该题解的核心思路是首先创建一个与输入字符串 `s` 等长的列表 `ans`，用于存储最终结果。接着，使用一个布尔列表 `rem` 来标记每个位置的字符是否为元音字母。同时，创建一个集合 `aei` 存储所有元音字母的小写和大写形式，用于快速判断某个字符是否为元音。在遍历字符串 `s` 的过程中，如果发现元音字母，则在 `rem` 中相应位置标记为 `True`，并将该元音字母添加到列表 `col` 中。遍历完成后，对 `col` 进行排序，按照 ASCII 值逆序排序。最后，再次遍历字符串，根据 `rem` 中的标记，从 `col` 中取出排序后的元音字母填充到 `ans` 中的相应位置。最终通过 `join` 方法将列表 `ans` 转换为字符串形式返回。

O(n + v log v)

O(n)