Watch 10 video solutions for Sort Vowels in a String, a medium level problem involving String, Sorting. This walkthrough by codestorywithMIK has 9,270 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a 0-indexed string s, permute s to get a new string t such that:
i with 0 <= i < s.length such that s[i] is a consonant, then t[i] = s[i].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 <= 105s consists only of letters of the English alphabet in uppercase and lowercase.Problem Overview: You are given a string and need to sort only the vowels (a, e, i, o, u in both lowercase and uppercase). Consonants must stay in their original positions. The final string should have vowels appearing in sorted ASCII order while every non-vowel character remains unchanged.
Approach 1: Two-Pass Extraction and Sorting (O(n + k log k) time, O(k) space)
Scan the string once and collect all vowel characters into a separate list. The number of vowels is k. Sort this list using a standard sorting algorithm, which costs O(k log k). In a second pass over the string, whenever you encounter a vowel, replace it with the next element from the sorted list.
The key insight: consonants never move, so you only manipulate the subset of vowel characters. The first pass isolates the data that needs ordering, and the second pass reinserts it while preserving original positions of non-vowels. This approach is simple to reason about and works well with languages that provide efficient built-in sort utilities. It heavily relies on basic string traversal and sorting.
Approach 2: In-Place Modification with Two Pointers (O(n + k log k) time, O(k) space)
Convert the string into a mutable character array. First gather and sort the vowels exactly as in the previous approach. Instead of rebuilding a new string, maintain a pointer that walks through the sorted vowel list while scanning the original array. Whenever a vowel position appears, overwrite it with the next sorted vowel.
The "two pointers" idea comes from tracking two sequences simultaneously: one pointer scans the string while another consumes the sorted vowel array. This avoids building an entirely new result string and modifies the character array directly. It is still dominated by the vowel sort step (O(k log k)) but keeps the code tight and memory usage predictable. This pattern commonly appears in problems involving two pointers and selective character replacement.
Recommended for interviews: The two-pass extraction and sorting approach is the clearest solution and usually what interviewers expect first. It demonstrates that you can isolate relevant elements, apply sorting, and rebuild the result efficiently. The in-place pointer variant shows stronger control over memory and iteration patterns, which signals deeper comfort with string manipulation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass Extraction and Sorting | O(n + k log k) | O(k) | Best general solution. Clear logic and easy to implement with built-in sorting. |
| In-Place Modification with Two Pointers | O(n + k log k) | O(k) | When you want to avoid constructing a new string and update characters directly. |