Sponsored
Sponsored
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.
1import java.util.*;
2
3public class SortVowels {
4 public static boolean isVowel(char c) {
5 c = Character.toLowerCase(c);
6 return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
7 }
8
9 public static String sortVowelsInString(String s) {
10 List<Character> vowels = new ArrayList<>();
11 for (char c : s.toCharArray()) {
12 if (isVowel(c)) {
13 vowels.add(c);
14 }
15 }
16 Collections.sort(vowels);
17
18 StringBuilder result = new StringBuilder(s);
19 int vowelIndex = 0;
20 for (int i = 0; i < s.length(); i++) {
21 if (isVowel(s.charAt(i))) {
22 result.setCharAt(i, vowels.get(vowelIndex++));
23 }
24 }
25 return result.toString();
26 }
27
28 public static void main(String[] args) {
29 String test = "lEetcOde";
30 System.out.println(sortVowelsInString(test));
31 }
32}This Java implementation uses a List to store vowels for automatic resizing. The vowels are sorted using Collections.sort(). A StringBuilder is used to reconstruct the output string with 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.
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.