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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) for in-place sorting of vowels.
Space Complexity: O(1) due to in-place modification.
| 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. |
LeetCode 1641. Count Sorted Vowel Strings - Interview Prep Ep 114 • Fisher Coder • 2,274 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