LeetCode 2785 - Sort Vowels in a String

Difficulty: 🟡 Medium
Topics: String, Sorting

Solution

Problem Understanding

This problem requires us to reorder the vowels in a string while keeping all consonants in their original positions. In simpler terms, we are asked to extract all vowels from a string, sort them by their ASCII values, and then put them back in their original positions, leaving consonants untouched.

The input s is a string containing only English letters in both lowercase and uppercase. The output is another string of the same length, with consonants unchanged and vowels sorted. The constraints indicate that s can have up to 100,000 characters, which implies that we need an algorithm that runs efficiently in linearithmic or linear time.

Important edge cases include strings with no vowels (where the output should be identical to the input), strings where all characters are vowels (where the output is simply the sorted string), and strings with mixed uppercase and lowercase vowels, since ASCII ordering treats uppercase letters as smaller than lowercase ones.

Approaches

The brute-force approach is straightforward: we could iterate over the string, collect all vowels in a list, sort them using a built-in sort function, and then iterate over the string a second time to place the sorted vowels back in their original positions. This approach is correct but requires multiple passes over the string, making it slightly inefficient, though acceptable for the input limits.

The optimal approach leverages the same idea but focuses on minimizing operations and keeping the algorithm simple and readable. First, we identify vowels while scanning the string once and store them in a list. Then we sort the vowels once using an efficient sorting algorithm. Finally, we perform a second pass to construct the resulting string by replacing vowels in order with the sorted ones. This approach is both simple and efficient and guarantees correctness due to the stable mapping of vowels to their positions.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Collect vowels, sort, then replace
Optimal	O(n log n)	O(n)	Single scan to collect vowels, sort, single scan to rebuild string

Algorithm Walkthrough

Initialize a set of vowels for quick membership checking. Include both uppercase and lowercase letters: {'a','e','i','o','u','A','E','I','O','U'}.
Traverse the string once to collect all vowels into a list in the order they appear. This preserves their original positions for replacement.
Sort the collected vowels list by ASCII value. Sorting ensures that the smallest ASCII vowels are placed first while maintaining overall order.
Initialize an empty list to build the result string. Iterate through the original string, and for each character, check if it is a vowel. If it is, replace it with the next vowel from the sorted list. Otherwise, append the consonant as-is.
Join the list of characters to form the final string and return it.

Why it works: The algorithm guarantees correctness because it only reorders vowels and leaves consonants in place. Sorting the vowels before reinsertion ensures that they appear in nondecreasing ASCII order while the positions of consonants remain unchanged.

Python Solution

class Solution:
    def sortVowels(self, s: str) -> str:
        vowels_set = {'a','e','i','o','u','A','E','I','O','U'}
        vowels = [ch for ch in s if ch in vowels_set]
        vowels.sort()
        
        result = []
        vowel_index = 0
        for ch in s:
            if ch in vowels_set:
                result.append(vowels[vowel_index])
                vowel_index += 1
            else:
                result.append(ch)
        return ''.join(result)

The implementation first defines a set of vowels for quick membership checks. Then, it uses a list comprehension to extract all vowels from s and sorts them. During the reconstruction phase, we iterate through the original string, appending either a sorted vowel or the consonant to the result list. Finally, we join the list into a string.

Go Solution

import (
    "sort"
    "strings"
)

func sortVowels(s string) string {
    vowelsSet := map[rune]bool{
        'a': true, 'e': true, 'i': true, 'o': true, 'u': true,
        'A': true, 'E': true, 'I': true, 'O': true, 'U': true,
    }

    var vowels []rune
    for _, ch := range s {
        if vowelsSet[ch] {
            vowels = append(vowels, ch)
        }
    }

    sort.Slice(vowels, func(i, j int) bool { return vowels[i] < vowels[j] })

    result := make([]rune, 0, len(s))
    vowelIndex := 0
    for _, ch := range s {
        if vowelsSet[ch] {
            result = append(result, vowels[vowelIndex])
            vowelIndex++
        } else {
            result = append(result, ch)
        }
    }

    return string(result)
}

In Go, we use a map[rune]bool for vowel lookup and a rune slice to store and sort vowels. The sorted vowels are then placed back into their positions using a second iteration. We preallocate the result slice for efficiency.

Worked Examples

Example 1: "lEetcOde"

Extract vowels: ['E','e','O']
Sort vowels: ['E','O','e']
Rebuild string:

'l' → 'l'
'E' → 'E'
'e' → 'O'
't' → 't'
'c' → 'c'
'O' → 'e'
'd' → 'd'
'e' → 'e'

Result: "lEOtcede"

Example 2: "lYmpH"

Extract vowels: []
Sort vowels: []
Rebuild string: all consonants remain the same.

Result: "lYmpH"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Extracting vowels is O(n), sorting vowels is O(k log k) where k ≤ n, rebuilding string is O(n). Overall dominated by sort.
Space	O(n)	Storing vowels and the result string list require O(n) space.

The algorithm efficiently handles large strings because the sorting step is performed only on vowels, which is generally fewer than total characters, and the two passes over the string are linear.

Test Cases

# Provided examples
assert Solution().sortVowels("lEetcOde") == "lEOtcede"  # mixed case vowels
assert Solution().sortVowels("lYmpH") == "lYmpH"        # no vowels

# Edge cases
assert Solution().sortVowels("aeiou") == "aeiou"        # all vowels already sorted
assert Solution().sortVowels("uoiea") == "aeiou"        # all vowels, reverse order
assert Solution().sortVowels("BCDFG") == "BCDFG"        # all consonants
assert Solution().sortVowels("aAbBeEiIoOuU") == "AAEEIIOOUU"  # mixed case vowels
assert Solution().sortVowels("zYxWuVt") == "zYxWuVt"    # consonants only

# Larger case
long_s = "a" * 50000 + "e" * 50000
assert Solution().sortVowels(long_s) == "a" * 50000 + "e" * 50000

Test	Why
`"lEetcOde"`	Validates mixed case vowel sorting
`"lYmpH"`	Validates no vowel case
`"aeiou"`	Already sorted vowels
`"uoiea"`	All vowels in reverse order
`"BCDFG"`	Only consonants
`"aAbBeEiIoOuU"`	Mixed case, multiple vowels
`"zYxWuVt"`	Only consonants with mixed case
Large string of vowels	Tests performance and correctness on large input

Edge Cases

The first important edge case is a string containing no vowels, such as "BCDFG". A naive implementation might attempt to sort an empty list incorrectly or fail to handle an empty vowels list. Our solution correctly leaves the string unchanged.

The second edge case involves a string of only vowels in mixed uppercase and lowercase, like "aAbBeEiIoOuU". The algorithm ensures that the ASCII order is respected, so uppercase vowels (smaller ASCII) appear before lowercase vowels when sorted.

The third edge case is very long strings, close to the upper limit of 105 characters. The solution handles this efficiently because we only perform sorting on vowels and linear passes on the string, making it feasible within typical time constraints for LeetCode.