2785. Sort Vowels in a String

Description

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.

 

Solutions

Solution: Hash Map

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} s
 * @return {string}
 */
const sortVowels = function (s) {
  const n = s.length;
  const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
  const vowelMap = { A: 0, E: 0, I: 0, O: 0, U: 0, a: 0, e: 0, i: 0, o: 0, u: 0 };

  const isVowel = char => vowels.has(char.toLowerCase());

  for (const char of s) {
    if (isVowel(char)) {
      vowelMap[char] += 1;
    }
  }

  const counts = Object.entries(vowelMap);
  const result = s.split('');
  let currentVowel = 0;

  for (let index = 0; index < n; index++) {
    if (!isVowel(s[index])) continue;

    while (!counts[currentVowel][1]) {
      currentVowel += 1;
    }

    result[index] = counts[currentVowel][0];
    counts[currentVowel][1] -= 1;
  }

  return result.join('');
};