Sort Vowels in a String

medium string sorting

Problem

You are given a string s of uppercase and lowercase English letters. Build a new string t of the same length where every consonant keeps exactly the position it had in s, while the vowels (a, e, i, o, u in either case) are rearranged among the vowel positions so that their ASCII values are in nondecreasing order.

Remember that every uppercase vowel has a smaller ASCII value than every lowercase vowel, so for example 'E' and 'O' must come before 'e'.

Inputs = "lEetcOde"

Output"lEOtcede"

The vowels E, e, O, e sort by ASCII to E, O, e, e and refill slots 1, 2, 5, 7; consonants l, t, c, d never move.

s (English letters only, max 16)

def sort_vowels(s):
    vowels = set("aeiouAEIOU")
    picked = [c for c in s if c in vowels]
    picked.sort()
    out = []
    k = 0
    for c in s:
        if c in vowels:
            out.append(picked[k])
            k += 1
        else:
            out.append(c)
    return "".join(out)

function sortVowels(s) {
  const vowels = new Set("aeiouAEIOU");
  const picked = [...s].filter(c => vowels.has(c));
  picked.sort();
  let k = 0;
  let out = "";
  for (const c of s) {
    if (vowels.has(c)) {
      out += picked[k++];
    } else {
      out += c;
    }
  }
  return out;
}

String sortVowels(String s) {
    String vs = "aeiouAEIOU";
    List<Character> picked = new ArrayList<>();
    for (char c : s.toCharArray())
        if (vs.indexOf(c) >= 0) picked.add(c);
    Collections.sort(picked);
    StringBuilder out = new StringBuilder();
    int k = 0;
    for (char c : s.toCharArray()) {
        if (vs.indexOf(c) >= 0) out.append(picked.get(k++));
        else out.append(c);
    }
    return out.toString();
}

string sortVowels(string s) {
    string vs = "aeiouAEIOU";
    string picked;
    for (char c : s)
        if (vs.find(c) != string::npos) picked += c;
    sort(picked.begin(), picked.end());
    int k = 0;
    for (char &c : s)
        if (vs.find(c) != string::npos) c = picked[k++];
    return s;
}

Explanation

The key observation is that the consonants are frozen and the multiset of vowels never changes — only the order of the vowels among their own slots does. That decouples the problem into three independent jobs: extract the vowels, sort them, and pour them back into the same slots from left to right.

Sorting "by ASCII" is the one detail that trips people up: every uppercase vowel ('A'–'U', codes 65–85) is smaller than every lowercase vowel ('a'–'u', codes 97–117). So a plain character sort already does the right thing — 'E' < 'O' < 'e' — and no case-folding is needed (or wanted).

Walk through the default example s = "lEetcOde". The scan collects the vowels in their original order: [E, e, O, e] at indices 1, 2, 5, 7. Sorting gives [E, O, e, e]. The second pass copies consonants unchanged and, every time it lands on a vowel slot, writes the next sorted vowel: index 1 gets 'E', index 2 gets 'O', index 5 gets 'e', index 7 gets 'e' — producing "lEOtcede".

Why does the refill pass guarantee a sorted result? The vowel slots are visited left to right, and the sorted list is consumed front to back with the pointer k. So the i-th vowel slot from the left receives the i-th smallest vowel — exactly the nondecreasing ASCII order the problem demands.

The cost is dominated by sorting the vowels: O(n log n) in the worst case where almost every character is a vowel, plus two linear passes. Since there are only 10 distinct vowel characters, you could even replace the sort with a counting sort over those 10 buckets to get a true O(n) solution; the space stays O(n) for the extracted vowels and the output.

Time: O(n log n) Space: O(n)