2785

2785. Sort Vowels in a String (Medium)

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.

Related Topics:
String, Sorting

Similar Questions:

• Reverse Vowels of a String (Easy)

Hints:

• Add all the vowels in an array and sort the array.
• Replace characters in string s if it's a vowel from the new array.

Solution 1.

// OJ: https://leetcode.com/problems/sort-vowels-in-a-string
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
    bool isVowel(char c) {
        c = tolower(c);
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
public:
    string sortVowels(string s) {
        vector<int> id;
        for (int i = 0; i < s.size(); ++i) {
            if (isVowel(s[i])) id.push_back(i);
        }
        sort(begin(id), end(id), [&](int a, int b) { return s[a] < s[b]; });
        string ans;
        for (int i = 0, j = 0; i < s.size(); ++i) {
            if (isVowel(s[i])) ans += s[id[j++]];
            else ans += s[i];
        }
        return ans;
    }
};