2785. Sort Vowels in a String
Problem Description
The problem requires us to modify a given string s
by permuting only the vowels, such that the vowels are sorted based on their ASCII values, while all the consonants remain in their original positions. Both uppercase and lowercase vowels ('a', 'e', 'i', 'o', 'u') should be considered, but it's important to note that consonants account for any letter that is not a vowel. The objective is to return the new string after the vowels have been sorted and the consonants are left untouched.
For example, if s
is "leetcode", the output should be "leotcede" because the vowels 'e','e','e','o' in s
are sorted to 'e','e','o','e' in the new string t
.
Intuition
The key intuition behind the solution is to separate the vowels from the consonants, sort the vowels according to their ASCII values, and then merge them back into the original string in their proper index locations.
-
Separating Vowels from Consonants: We go through the string
s
and create a list of vowels. This is done by checking if each character is a vowel (for simplicity, by checking if it's in the string "aeiou" after converting to lowercase to ensure that both uppercase and lowercase vowels are considered). -
Sorting Vowels: Once we have a list that contains only the vowels from the original string, we sort this list. This sorted list now represents the order that the vowels should appear in the final string.
-
Merging Vowels Back: Keeping a separate copy of the original string allows us to know the positions of the consonants, so we can replace the vowels in this copy with the sorted vowels. We iterate through the copy of the original string and each time we encounter a vowel, we take the next vowel from our sorted vowels list and replace it.
-
Converting to String: Finally, we join the list into a string and return this as our final sorted string with the vowel positions permuted according to their ASCII values and consonants in their initial places.
Learn more about Sorting patterns.
Solution Approach
The solution approach for sorting the vowels in the string while keeping the consonants in place involves a few clear steps combining algorithmic thinking and data structures.
Algorithm:
-
Collecting Vowels: Iterate over the input string
s
and build a list of vowels calledvs
. This is achieved using a list comprehension that includes a characterc
only ifc.lower()
is found within the string "aeiou". This step effectively filters out consonants. -
Sorting Vowels: Once we have a list of all the vowels from the string, sort this list using Python's built-in
sort()
method. The sortedvs
list now contains the vowels in the order they should appear in the resulting string based on their ASCII values. -
Preparing for Re-insertion: Copy the original string
s
into a listcs
which will allow modifying individual characters at specific indices (since strings in Python are immutable). -
Inserting Sorted Vowels: We will use two pointersā
i
iterating over thecs
list which represents the original string's characters, andj
which keeps track of the position in the sorted vowels listvs
. When we encounter a vowel (as determined byc.lower()
in "aeiou") incs
at the current indexi
, we replace it with the vowel at the current indexj
from the sorted listvs
. We then incrementj
to move to the next sorted vowel. -
Joining the List: After iterating through the entire list and replacing vowels with their sorted counterparts, we join the list
cs
back into a string using"".join(cs)
, which gives us the final string where vowels are sorted, and consonants remain in their original places.
Data Structures:
- List for Vowels: We use a list to keep all the vowels from the original string because lists in Python are mutable and can be sorted easily.
- List for Modifying String: A list (
cs
) copying the original strings
is also created to modify the characters in-place, as strings in Python are immutable and cannot be changed after creation. - For-Loop with Enumeration: The use of
enumerate
oncs
provides both index and character in a single loop, which is efficient for tracking positions for vowel replacement. - Index Pointer (
j
): A counter variablej
is used to traverse thevs
list while placing sorted vowels back intocs
.
Code Reference:
class Solution:
def sortVowels(self, s: str) -> str:
vs = [c for c in s if c.lower() in "aeiou"] # Collecting vowels
vs.sort() # [Sorting](/problems/sorting_summary) vowels
cs = list(s) # Copy string to a list
j = 0 # Pointer for sorted vowels list
for i, c in enumerate(cs): # Loop through characters in original string
if c.lower() in "aeiou": # If character is a vowel
cs[i] = vs[j] # Replace with sorted vowel
j += 1 # Move to next vowel in sorted list
return "".join(cs) # Return modified string as output
This code snippet clearly follows the approach and uses the necessary data structures to accomplish the task.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach using the string s = "contribute"
.
-
Collecting Vowels: We go through each character in "contribute" and collect the vowels in the list
vs
. After iterating over the string,vs
becomes['o', 'i', 'u', 'e']
. -
Sorting Vowels: Sorting the list
vs
gives us['e', 'i', 'o', 'u']
. -
Preparing for Re-insertion: We convert the original string
s
into a listcs
which will let us modify individual characters. So,cs
becomes['c', 'o', 'n', 't', 'r', 'i', 'b', 'u', 't', 'e']
. -
Inserting Sorted Vowels: As we iterate over
cs
, when we find a vowel, we replace it with the next vowel from the sorted listvs
. After processing,cs
now looks like['c', 'e', 'n', 't', 'r', 'i', 'b', 'o', 't', 'u']
. -
Joining the List: Finally, we join
cs
back into a string to get the outputceotributn
.
Following these steps with our example, the original string contribute
transforms into ceotributn
where the vowels appear in sorted order based on their ASCII values while all consonants remain in their original positions.
Solution Implementation
1class Solution:
2 def sortVowels(self, s: str) -> str:
3 # Initialize an array to hold the vowels from the string
4 vowels = [c for c in s if c.lower() in "aeiou"]
5
6 # Sort the vowels array in alphabetical order
7 vowels.sort()
8
9 # Convert the input string to a list to enable modifications
10 characters = list(s)
11
12 # Initialize a counter for the vowels array index
13 vowel_index = 0
14
15 # Iterate through the characters of the string
16 for i, c in enumerate(characters):
17 # Check if the character is a vowel
18 if c.lower() in "aeiou":
19 # Replace the vowel in the characters array with the sorted one
20 characters[i] = vowels[vowel_index]
21 # Increment the vowel index to move to the next sorted vowel
22 vowel_index += 1
23
24 # Join the characters back to form the modified string and return
25 return "".join(characters)
26
1class Solution {
2 // Method to sort vowels in a given string
3 // Vowels in the original string are replaced with vowels in sorted order
4 public String sortVowels(String s) {
5 // List to store vowels
6 List<Character> vowels = new ArrayList<>();
7 // Convert the string to a character array
8 char[] chars = s.toCharArray();
9 // Iterate over the character array
10 for (char c : chars) {
11 // Convert character to lower case to handle both cases
12 char lowerCase = Character.toLowerCase(c);
13 // Check if the character is a vowel
14 if (lowerCase == 'a' || lowerCase == 'e' || lowerCase == 'i' || lowerCase == 'o' || lowerCase == 'u') {
15 // Add vowel to the list
16 vowels.add(c);
17 }
18 }
19 // Sort the list of vowels
20 Collections.sort(vowels);
21 // Initialize an index to keep track of sorted vowels
22 int vowelIndex = 0;
23 // Replace vowels in the original array with vowels in sorted order
24 for (int i = 0; i < chars.length; ++i) {
25 // Convert character to lower case to handle both cases
26 char lowerCase = Character.toLowerCase(chars[i]);
27 // Check if the character is a vowel
28 if (lowerCase == 'a' || lowerCase == 'e' || lowerCase == 'i' || lowerCase == 'o' || lowerCase == 'u') {
29 // Replace the vowel with a sorted vowel from the list
30 chars[i] = vowels.get(vowelIndex++);
31 }
32 }
33 // Convert character array back to string and return
34 return String.valueOf(chars);
35 }
36}
37
1#include <algorithm> // Include algorithm header for std::sort
2#include <cctype> // Include cctype header for std::tolower
3
4class Solution {
5public:
6 // Function to sort vowels in a given string 's'
7 string sortVowels(string s) {
8 string vowels; // Initialize a string to store the found vowels
9
10 // Iterate over each character in the input string
11 for (auto c : s) {
12 // Convert each character to lowercase for comparison
13 char lowerCaseChar = std::tolower(c);
14
15 // Check if the character is a vowel
16 if (lowerCaseChar == 'a' || lowerCaseChar == 'e' ||
17 lowerCaseChar == 'i' || lowerCaseChar == 'o' ||
18 lowerCaseChar == 'u') {
19
20 vowels.push_back(c); // Add the vowel to the 'vowels' string
21 }
22 }
23
24 // Sort the vowels alphabetically
25 std::sort(vowels.begin(), vowels.end());
26
27 // Replace the vowels in the original string with sorted vowels
28 for (int i = 0, vowelIndex = 0; i < s.size(); ++i) {
29 // Check if the current character is a vowel
30 char lowerCaseChar = std::tolower(s[i]);
31 if (lowerCaseChar == 'a' || lowerCaseChar == 'e' ||
32 lowerCaseChar == 'i' || lowerCaseChar == 'o' ||
33 lowerCaseChar == 'u') {
34
35 // Replace the vowel with the sorted vowel from 'vowels'
36 s[i] = vowels[vowelIndex++];
37 }
38 }
39
40 return s; // Return the modified string with sorted vowels
41 }
42};
43
1// This function sorts the vowels in a given string while keeping the consonants in their original position
2function sortVowels(inputString: string): string {
3 // Define an array of all vowels, both lowercase and uppercase
4 const vowels: string[] = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'];
5
6 // Split the input string into characters, filter out vowels, and sort them
7 const sortedVowels: string[] = inputString
8 .split('')
9 .filter(character => vowels.includes(character))
10 .sort();
11
12 // Create an array to hold the final characters in the correct order
13 const sortedCharacters: string[] = [];
14
15 // Index for iterating over the sortedVowels
16 let vowelIndex: number = 0;
17
18 // Iterate over each character of the input string
19 for (const character of inputString) {
20 // If the character is a vowel, use the vowel from sortedVowels (preserving original order elsewise)
21 sortedCharacters.push(vowels.includes(character) ? sortedVowels[vowelIndex++] : character);
22 }
23
24 // Join the sorted characters array into a string and return it
25 return sortedCharacters.join('');
26}
27
28// Usage
29const input = "LeetCode";
30const sorted = sortVowels(input);
31console.log(sorted); // Expected output would have vowels sorted within the string
32
Time and Space Complexity
Time Complexity
The provided Python code consists of the following operations:
-
Creating a list of vowels (
vs
): This involves iterating over each character in the strings
to check if it is a vowel, which takesO(n)
time wheren
is the length of the string. -
Sorting the list of vowels (
vs.sort()
): The time complexity for sorting in Python (using Timsort) isO(m log m)
wherem
is the number of vowels in the string, which is at mostn
. -
Iterating over the string characters and replacing vowels (
for i, c in enumerate(cs)
): We iterate over the listcs
once, which takesO(n)
time. For each vowel, we perform a constant-time operation.
Combining these steps, the overall time complexity is O(n) + O(m log m) + O(n)
. Since m
is at most n
, the time complexity can be simplified to O(n) + O(n log n)
, which is dominated by the sorting step, leading to a final time complexity of O(n log n)
.
Space Complexity
The space complexity is determined by the additional space used by the algorithm, not including the input itself:
-
List of vowels (
vs
): At mostn
if the string consists only of vowels, soO(n)
space. -
List of characters from the string (
cs
): We create a list of all characters, which also takesO(n)
space. -
The sorted list of vowels does not use extra space because the sorting is done in-place on the
vs
list.
Therefore, the combined space complexity is O(n)
for storing the vowels and O(n)
for storing the character array, which totals O(2n)
. Simplifying this gives us O(n)
space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following uses divide and conquer strategy?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!