We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sort Vowels in a String

Difficulty: Medium

Problem Description

Given a 0-indexed string s, permute s to get a new string t such that:

  • All consonants remain in their original places.
  • The vowels must be sorted in the nondecreasing order of their ASCII values.

Return the resulting string.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in lowercase or uppercase. Consonants comprise all letters that are not vowels.

Key Insights

  • Identify and separate vowels from consonants in the string.
  • Sort the vowels based on their ASCII values.
  • Reconstruct the string by placing sorted vowels back in their original positions, while keeping consonants fixed.

Space and Time Complexity

Time Complexity: O(n log n) - due to the sorting of vowels. Space Complexity: O(n) - for storing the vowels and the resulting string.

Solution

To solve the problem, we will follow these steps:

  1. Traverse the string to identify and extract vowels while keeping track of their positions.
  2. Sort the extracted vowels.
  3. Create a new result string by iterating through the original string, placing the sorted vowels in their original positions and retaining consonants as they are.

We will use a list to store the vowels and their indices for sorting, and a character array to build the final result efficiently.

Code Solutions

def sortVowels(s: str) -> str:
    vowels = 'aeiouAEIOU'
    vowel_list = []
    indices = []
    
    # Extract vowels and their indices
    for i, char in enumerate(s):
        if char in vowels:
            vowel_list.append(char)
            indices.append(i)
    
    # Sort the vowels
    vowel_list.sort()
    
    # Convert the string to a list for mutation
    result = list(s)
    
    # Place sorted vowels back into their original positions
    for index, vowel in zip(indices, vowel_list):
        result[index] = vowel
    
    return ''.join(result)
← Back to All Questions