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.
1function isVowel(c) {
2 return 'aeiouAEIOU'.includes(c);
3}
4
5function sortVowelsInString(s) {
6 const vowels = [...s].filter(isVowel);
7 vowels.sort();
8 let vowelIndex = 0;
9 return Array.from(s).map(c => isVowel(c) ? vowels[vowelIndex++] : c).join('');
10}
11
12// Test
13const s = "lEetcOde";
14console.log(sortVowelsInString(s));This JavaScript implementation identifies vowels using the filter() method and maintains order with the Array.sort(). It reconstructs the string using map() to replace only vowel positions, integrating sorted 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.
Time Complexity: O(n^2) for in-place sorting of vowels.
Space Complexity: O(1) due to in-place modification.
1public class SortVowelsInPlace {
2 public static boolean isVowel(char c) {
3 c = Character.toLowerCase(c);
4 return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
5 }
6
7 public static String sortVowelsInPlace(String s) {
8 char[] chars = s.toCharArray();
9 int left = 0, right = chars.length - 1;
10 while (left < right) {
11 while (left < right && !isVowel(chars[left])) left++;
12 while (left < right && !isVowel(chars[right])) right--;
13 if (left < right && chars[left] > chars[right]) {
14 char temp = chars[left];
15 chars[left] = chars[right];
16 chars[right] = temp;
17 }
18 left++;
19 right--;
20 }
21 return new String(chars);
22 }
23
24 public static void main(String[] args) {
25 String test = "lEetcOde";
26 System.out.println(sortVowelsInPlace(test));
27 }
28}This Java approach tackles efficient in-place sorting of vowels via a two-pointer method aiming at minimal modification cost and ensuring consonant positions remain unaffected.