Sort Vowels in a String

Sort Vowels in a String

What is this problem about?

"Sort Vowels in a String" is a string manipulation challenge where you are asked to identify all the vowels in a given string and rearrange them so that they appear in ascending order of their ASCII values. Crucially, all consonants and other characters must remain in their original positions.

For example, if the string is "lEetcOde", the vowels are ['E', 'e', 'O', 'e']. Their ASCII values are 69, 101, 79, 101. Sorted: [69, 79, 101, 101] -> ['E', 'O', 'e', 'e']. The final string would be "lEOtc0de" (with vowels replaced in sorted order).

Why is this asked in interviews?

Companies like Microsoft and Google use this coding problem to test your ability to filter and transform data selectively. It evaluates your familiarity with ASCII values (where uppercase comes before lowercase) and your proficiency with string traversal and reconstruction. It’s also a good exercise in managing multiple pointers or indices as you rebuild the final string.

Algorithmic pattern used

The algorithmic pattern used is Extraction, Sorting, and Re-insertion.

1. Scan: Iterate through the string and extract all vowels into a separate list.
2. Sort: Sort the extracted vowels in ascending order based on their ASCII codes.
3. Rebuild: Iterate through the original string again. If the current character is a vowel, replace it with the next vowel from the sorted list. If it’s a consonant, keep it as is.

Example explanation

Input: "Code"

1. Vowels found: ['o', 'e'].
2. ASCII values: 'e' (101), 'o' (111).
3. Sorted vowels: ['e', 'o'].
4. Rebuild:
   • 'C' is consonant: "C"
   • 'o' is vowel: Replace with 'e' -> "Ce"
   • 'd' is consonant: "Ced"
   • 'e' is vowel: Replace with 'o' -> "Cedo" Result: "Cedo".

Common mistakes candidates make

One common error is neglecting to handle both uppercase and lowercase vowels (A, E, I, O, U, a, e, i, o, u). Another mistake is inefficiently rebuilding the string using repeated concatenation, which is $O(N^2)$ in some languages. You should use a list of characters and then join them. Some candidates also forget that uppercase vowels come before lowercase vowels in the standard ASCII sequence, which affects the sort order.

Interview preparation tip

To excel in the "Sort Vowels in a String interview question," create a set of vowels for $O(1)$ lookups during the scan. Mentioning that sets provide faster check times than checking a list or using multiple if statements shows attention to performance. Also, practice in-place character replacement if you are working with a language that has mutable strings (like C++).