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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sort Vowels in a String

Number: 2887

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a 0-indexed string s, permute s to get a new string t such that all vowels in s are sorted in nondecreasing order according to their ASCII values while all consonants remain in their original positions. Vowels are defined as 'a', 'e', 'i', 'o', 'u' (both lowercase and uppercase).

Key Insights

  • Extract vowels from the input string while maintaining their order.
  • Sort the extracted vowels based on their ASCII values.
  • Reconstruct the string by replacing each vowel position with the next vowel from the sorted list, leaving consonants unchanged.

Space and Time Complexity

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

Solution

The solution involves a two-pass approach. In the first pass, iterate over the string and collect all vowels in a list. Then sort this list to arrange vowels in nondecreasing order based on their ASCII values. In the second pass, iterate over the string again and for every vowel encountered, replace it with the next vowel from the sorted list while leaving consonants intact. This approach makes use of additional space to store the vowels and the result but ensures that the positions of consonants remain unchanged.

Code Solutions

# Function to check if a character is a vowel.
def is_vowel(ch):
    return ch.lower() in 'aeiou'

def sortVowels(s):
    # Extract vowels from the string.
    vowels = [ch for ch in s if is_vowel(ch)]
    # Sort the list of vowels by ASCII values.
    vowels.sort()
    result = []  # List to store the final characters.
    vowel_index = 0  # To track the index in the sorted vowels list.
    
    # Construct the result string.
    for ch in s:
        if is_vowel(ch):
            result.append(vowels[vowel_index])
            vowel_index += 1
        else:
            result.append(ch)
    
    return ''.join(result)

# Example usage:
print(sortVowels("lEetcOde"))
← Back to All Questions