Abstract / Summary

Take all vowels from the string, sort them, then put them back into the string in order.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 80% (100k+ submissions).

Typical patterns to solve this problem:

• Sorting
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a single method sortVowels. The method receives a string s and returns a new string where all vowel characters are reordered in ascending alphabetical order while every non-vowel character retains its original position. The algorithm proceeds in three conceptual phases: identification of vowel characters, sorting of the collected vowels, and reconstruction of the final string by merging the sorted vowels back into their original slots.

Identification of Vowel Characters

The first logical block creates a set containing both uppercase and lowercase vowel symbols. A set is chosen because membership tests (c in vowels) execute in constant time, which is advantageous when scanning the input string character by character.

vowels = set([ "A", "E", "I", "O", "U", "a", "e", "i", "o", "u" ])

During the scan, a list comprehension extracts every character from s that belongs to the vowel set. The comprehension iterates over the entire input once, producing a list of vowel characters in the order they appear.

v = sorted([ c for c in s if c in vowels ])

Because the comprehension filters directly on the set, characters that are not vowels are ignored without additional conditional branches, simplifying the extraction step.

Sorting the Collected Vowels

The built-in sorted function is applied to the list of extracted vowels. This call leverages Python’s highly optimized Timsort algorithm, which adapts to existing order in the data and runs efficiently for typical inputs. The result is a new list v that contains the same vowel characters but arranged from the smallest Unicode code point to the largest, effectively sorting them alphabetically while preserving case distinctions.

Reconstruction of the Result String

String immutability in Python makes repeated concatenation costly. To avoid this, the algorithm constructs a mutable list named result and appends characters one by one. Two variables drive the reconstruction: used, an index into the sorted vowel list, and the loop variable c, each character from the original string.

result = []
used = 0
for c in s:
    if c in vowels:
        result.append(v[used])
        used += 1
    else:
        result.append(c)

When the current character c is a vowel, the algorithm substitutes it with the next vowel from the sorted list (v[used]) and increments used. For consonants and any other non-vowel symbols, the original character is appended unchanged. This approach guarantees that the relative positions of non-vowel characters remain intact while the vowel positions are filled with the sorted sequence.

After the loop finishes, the list result holds the complete sequence of characters for the final output. The list is then joined into a single string using the efficient str.join method, which performs a single allocation for the final string.

return "".join(result)

Edge Cases Handled

The algorithm gracefully manages several boundary conditions without special-case code. An empty input string results in an empty list from the comprehension, an empty sorted list, and consequently an empty result list; the final join returns an empty string. When the input contains no vowel characters, the comprehension yields an empty list, the sorted list v is empty, and the loop never attempts to access v[used] because the if c in vowels branch is never taken. Conversely, if the input consists solely of vowels, the comprehension captures every character, the sorted list contains all of them, and the reconstruction loop replaces each character with the next sorted vowel, effectively returning the fully sorted version of the original string. Mixed-case inputs are handled because the vowel set includes both uppercase and lowercase symbols, and the sorting respects the Unicode ordering, placing uppercase vowels before their lowercase counterparts when they share the same letter.

Performance Optimizations Observed

The code exhibits several deliberate choices that improve runtime efficiency. The use of a set for vowel lookup reduces the cost of membership checks from linear to constant time, which is significant when processing long strings. The list comprehension for vowel extraction avoids the overhead of manual index management and leverages Python’s internal iteration mechanisms. By delegating the sorting work to the built-in sorted function, the implementation benefits from a highly tuned sorting routine that adapts to partially ordered data. The reconstruction phase avoids repeated string concatenation by accumulating characters in a list and performing a single join operation at the end, thereby minimizing memory reallocations. Finally, the single pass over the original string in the reconstruction loop ensures that each character is examined only once after the initial vowel extraction, keeping the overall processing linear with respect to the input length.

Imagine there is a big pile of scattered letters that make up a word. Some are vowels like a, e, i, o, and u, and the others are the plain consonants. Think of this code as a helper who wants to organize all those vowels.

First, the helper looks at the word and grabs every single vowel it can find. It lines them all up in alphabetical order, just like how you might organize toys from smallest to biggest.

Next, the helper starts building a brand new word by looking at the original one letter at a time. When it sees a consonant, it just puts that letter directly into the new word exactly where it was before. But when it sees a place where a vowel used to be, it reaches into its sorted line of vowels and picks the very first one. Then it picks the second one, and the third one, and keeps going until all the vowels are in their new, tidy order.

At the end, all the regular letters are still in their original spots, but all the vowels have hopped around to be in alphabetical order.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Java	C++			Python		TS
	WalkCCC		Java	C++			Python
	leetcode.ca		Java	C++	C#	Go	Python	Rust	TS
	Progiez		Java	C++			Python
github	charles-wangkai		Java
	fsq			C++
	JoshCrozier	JS
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality