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.
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.
1#include <stdio.h>
2#include <string.h>
3#include <ctype.h>
4
5int isVowel(char c) {
6 c = tolower(c);
7 return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
8}
9
10void sortVowels(char *vowels, int n) {
11 for (int i = 0; i < n-1; i++) {
12 for (int j = i+1; j < n; j++) {
13 if (vowels[i] > vowels[j]) {
14 char temp = vowels[i];
15 vowels[i] = vowels[j];
16 vowels[j] = temp;
17 }
18 }
19 }
20}
21
22char* sortVowelsInString(const char *s) {
23 int len = strlen(s);
24 char *result = (char *)malloc((len + 1) * sizeof(char));
25 char vowels[100000];
26 int indices[100000];
27 int vowelCount = 0;
28
29 for (int i = 0; i < len; i++) {
30 result[i] = s[i];
31 if (isVowel(s[i])) {
32 vowels[vowelCount] = s[i];
33 indices[vowelCount++] = i;
34 }
35 }
36 sortVowels(vowels, vowelCount);
37
38 for (int i = 0; i < vowelCount; i++) {
39 result[indices[i]] = vowels[i];
40 }
41 result[len] = '\0';
42 return result;
43}
44
45int main() {
46 const char *test = "lEetcOde";
47 char *sorted = sortVowelsInString(test);
48 printf("%s\n", sorted);
49 free(sorted);
50 return 0;
51}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.
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.
Time Complexity: O(n^2) for in-place sorting of vowels.
Space Complexity: O(1) due to in-place modification.
1function isVowel(c) {
2 return 'aeiouAEIOU'.includes(c);
3}
4
5function sortVowelsInPlace(s) {
6 const chars = s.split('');
7 let left = 0, right = chars.length - 1;
8 while (left < right) {
9 while (left < right && !isVowel(chars[left])) left++;
10 while (left < right && !isVowel(chars[right])) right--;
11 if (left < right && chars[left] > chars[right]) {
12 [chars[left], chars[right]] = [chars[right], chars[left]];
13 }
14 left++;
15 right--;
16 }
17 return chars.join('');
18}
19
20// Test
21const s = "lEetcOde";
22console.log(sortVowelsInPlace(s));This JavaScript method employs a two-pointer technique optimized for reducing extraneous space usage, aiming to sort and modify directly within the array representation of the string, advancing consonant maintenance invariant.