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.
1def is_vowel(c):
2 return c.lower() in 'aeiou'
3
4def sort_vowels_in_string(s):
5 vowels = [c for c in s if is_vowel(c)]
6 vowels.sort()
7 result = list(s)
8 v_index = 0
9 for i in range(len(result)):
10 if is_vowel(result[i]):
11 result[i] = vowels[v_index]
12 v_index += 1
13 return ''.join(result)
14
15# Test
16s = "lEetcOde"
17print(sort_vowels_in_string(s))This Python implementation uses list comprehensions to collect vowels and the list's sort method for sorting them. The function sort_vowels_in_string reconstructs the string using a list for efficient character assignment, and finally joins the list into a string to return the result.
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.