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.

  1. 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).

  2. 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.

  3. 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.

  4. 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:

  1. Collecting Vowels: Iterate over the input string s and build a list of vowels called vs. This is achieved using a list comprehension that includes a character c only if c.lower() is found within the string "aeiou". This step effectively filters out consonants.

  2. 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 sorted vs list now contains the vowels in the order they should appear in the resulting string based on their ASCII values.

  3. Preparing for Re-insertion: Copy the original string s into a list cs which will allow modifying individual characters at specific indices (since strings in Python are immutable).

  4. Inserting Sorted Vowels: We will use two pointersā€”i iterating over the cs list which represents the original string's characters, and j which keeps track of the position in the sorted vowels list vs. When we encounter a vowel (as determined by c.lower() in "aeiou") in cs at the current index i, we replace it with the vowel at the current index j from the sorted list vs. We then increment j to move to the next sorted vowel.

  5. 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 string s 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 on cs provides both index and character in a single loop, which is efficient for tracking positions for vowel replacement.
  • Index Pointer (j): A counter variable j is used to traverse the vs list while placing sorted vowels back into cs.

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 Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the string s = "contribute".

  1. 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'].

  2. Sorting Vowels: Sorting the list vs gives us ['e', 'i', 'o', 'u'].

  3. Preparing for Re-insertion: We convert the original string s into a list cs which will let us modify individual characters. So, cs becomes ['c', 'o', 'n', 't', 'r', 'i', 'b', 'u', 't', 'e'].

  4. Inserting Sorted Vowels: As we iterate over cs, when we find a vowel, we replace it with the next vowel from the sorted list vs. After processing, cs now looks like ['c', 'e', 'n', 't', 'r', 'i', 'b', 'o', 't', 'u'].

  5. Joining the List: Finally, we join cs back into a string to get the output ceotributn.

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:

  1. Creating a list of vowels (vs): This involves iterating over each character in the string s to check if it is a vowel, which takes O(n) time where n is the length of the string.

  2. Sorting the list of vowels (vs.sort()): The time complexity for sorting in Python (using Timsort) is O(m log m) where m is the number of vowels in the string, which is at most n.

  3. Iterating over the string characters and replacing vowels (for i, c in enumerate(cs)): We iterate over the list cs once, which takes O(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:

  1. List of vowels (vs): At most n if the string consists only of vowels, so O(n) space.

  2. List of characters from the string (cs): We create a list of all characters, which also takes O(n) space.

  3. 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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following uses divide and conquer strategy?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More