Sort Vowels in a String

Medium
1023.

Sort Vowels in a String

Sort Vowels in a String is a medium coding problem on strings and sorting, asked in Amazon, Google and Adobe interviews.

Rearrange s so that:

  • every consonant stays exactly where it was, and
  • the vowels — a, e, i, o, u in either case — are sorted into non-decreasing ASCII order among the positions they already occupy.

Return the resulting string. Note that all uppercase letters sort before all lowercase ones.

Example 1

Input
s = "codekairo"
Output
cadekioro
Explanation
The vowels `o,e,a,i,o` sort to `a,e,i,o,o` and refill positions 1, 3, 5, 6 and 8.

Example 2

Input
s = "lEetcOde"
Output
lEOtcede
Explanation
`E` (69) and `O` (79) come before the two lowercase `e`s (101).

Example 3

Input
s = "lYmpH"
Output
lYmpH
Explanation
No vowels, so nothing moves.

Constraints

  • 1 <= s.length <= 10^5
  • s consists only of letters of the English alphabet in uppercase and lowercase.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var sortVowels = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sort Vowels in a String — Solution in Python, Java & C++

Sort Vowels in a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Sort Vowels in a String is a medium coding problem on strings and sorting, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Medium
  • Topics: Strings, Sorting
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Rearrange s so that:

  • every consonant stays exactly where it was, and
  • the vowels — a, e, i, o, u in either case — are sorted into non-decreasing ASCII order among the positions they already occupy.

Return the resulting string. Note that all uppercase letters sort before all lowercase ones.

Example 1

Input: s = "codekairo"
Output: cadekioro
Explanation: The vowels `o,e,a,i,o` sort to `a,e,i,o,o` and refill positions 1, 3, 5, 6 and 8.

Example 2

Input: s = "lEetcOde"
Output: lEOtcede
Explanation: `E` (69) and `O` (79) come before the two lowercase `e`s (101).

Example 3

Input: s = "lYmpH"
Output: lYmpH
Explanation: No vowels, so nothing moves.

Constraints

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

Hints for Sort Vowels in a String

  1. Hint 1

    Pull the vowels out into a list, sort it, then put them back into the vowel positions in order.

  2. Hint 2

    Sorting is by ASCII code, so 'A' < 'E' < 'a' < 'e'.

  3. Hint 3

    There are only ten distinct vowel characters — a counting sort is linear.

How to solve Sort Vowels in a String

Extract the vowels, sort them, and write them back into the same positions left to right. Consonants are copied through untouched.

Approach

  1. Scan s, collecting every vowel into a list.
  2. Sort the list by character code.
  3. Rebuild the string: at a vowel position emit the next sorted vowel, otherwise the original character.

Why it works

The positions of the vowels never change — only which vowel sits in each — so the problem separates cleanly into "which slots" and "what order". With only ten possible vowel characters, tallying them and emitting in code order beats a comparison sort and makes the whole thing O(n).

Complexity

  • Time — O(n log n), or O(n) with a counting sort
  • Space — O(n)

Pitfalls

  • The order is by ASCII, so every uppercase vowel precedes every lowercase one — not case-insensitive alphabetical.
  • Consonants must not shift; only the vowel slots are refilled.
  • y is not a vowel here.

Reference solution

Python

def sortVowels(s: str) -> str:
    vowels = sorted(c for c in s if c in "aeiouAEIOU")
    it = iter(vowels)
    return "".join(next(it) if c in "aeiouAEIOU" else c for c in s)

Java

public static String sortVowels(String s) {
    String V = "aeiouAEIOU";
    List<Character> vowels = new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
        if (V.indexOf(s.charAt(i)) >= 0) vowels.add(s.charAt(i));
    }
    Collections.sort(vowels);
    StringBuilder sb = new StringBuilder();
    int k = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        sb.append(V.indexOf(c) >= 0 ? vowels.get(k++) : c);
    }
    return sb.toString();
}

C++

string sortVowels(string s) {
    string V = "aeiouAEIOU";
    string vowels;
    for (char c : s) {
        if (V.find(c) != string::npos) vowels += c;
    }
    sort(vowels.begin(), vowels.end());
    string out;
    size_t k = 0;
    for (char c : s) {
        out += (V.find(c) != string::npos) ? vowels[k++] : c;
    }
    return out;
}

JavaScript

var sortVowels = function(s) {
    var V = "aeiouAEIOU";
    var vowels = [], i;
    for (i = 0; i < s.length; i++) {
        if (V.indexOf(s.charAt(i)) !== -1) vowels.push(s.charAt(i));
    }
    vowels.sort();
    var out = "", k = 0;
    for (i = 0; i < s.length; i++) {
        out += V.indexOf(s.charAt(i)) !== -1 ? vowels[k++] : s.charAt(i);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Sorting Algorithms