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.
This approach consists of two main parts: identifying and sorting vowels, and reconstructing the string with sorted vowels while keeping consonants in their original places. In the first pass, we traverse the string to collect all the vowels and simultaneously record their indices. Then we sort the collected vowels. In the second pass, we construct the new string by placing the vowels back in their recorded positions in sorted order, while consonants are directly copied from the original string.
This C implementation defines a helper function isVowel() to check if a character is a vowel. Vowels are collected in an array, and their indices are stored separately. After sorting the vowels, the result string is constructed by keeping consonants in place and inserting sorted vowels at their respective original indices.
Time Complexity: O(n + m^2), where n is the length of the string and m is the number of vowels (due to sorting, which isn't optimized here to O(m log m)).
Space Complexity: O(n), where n is the length of the string for storing the result and vowels.
This in-place approach is optimized beyond the two-pass method using a two-pointer technique tailored for scenarios where vowels need to be sorted and replaced directly in the original string buffer. Instead of additional space for vowel storage and indexing, we identify vowels and simultaneously allow swapping to form sorted order based on ASCII comparison efficiently.
This C solution adopts a two-pointer approach for in-place sorting. The function iterates with two pointers, left and right, moving toward each other. It only swaps when conditions meet that vowels appear out of order according to ASCII values, making it simple and reducing additional space.
Time Complexity: O(n^2) for in-place sorting of vowels.
Space Complexity: O(1) due to in-place modification.
First, we store all the vowels in the string into an array or list vs, then we sort vs.
Next, we traverse the string s, keeping the consonants unchanged. If it is a vowel, we replace it in order with the letters in the vs array.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the string s.
| Approach | Complexity |
|---|---|
| Using Two-Pass and Sorting | Time Complexity: O(n + m^2), where n is the length of the string and m is the number of vowels (due to sorting, which isn't optimized here to O(m log m)). |
| In-Place Modification with Two Pointers | Time Complexity: O(n^2) for in-place sorting of vowels. |
| Sorting | — |
| 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. |
Sort Vowels in a String | 2 Approaches | Intuition | MICROSOFT | Leetcode-2785 • codestorywithMIK • 9,270 views views
Watch 9 more video solutions →Practice Sort Vowels in a String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor