Skip to main content
Talentd

Sort Vowels in a String - Solution & Explanation

MediumStringSorting19 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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

  • All consonants remain in their original places. More formally, if there is an index i with 0 <= i < s.length such that s[i] is a consonant, then t[i] = s[i].
  • The vowels must be sorted in the nondecreasing order of their ASCII values. More formally, for pairs of indices i, j with 0 <= i < j < s.length such that s[i] and s[j] are vowels, then t[i] must not have a higher ASCII value than t[j].

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.

 

Example 1:

Input: s = "lEetcOde"
Output: "lEOtcede"
Explanation: 'E', 'O', and 'e' are the vowels in s; 'l', 't', 'c', and 'd' are all consonants. The vowels are sorted according to their ASCII values, and the consonants remain in the same places.

Example 2:

Input: s = "lYmpH"
Output: "lYmpH"
Explanation: There are no vowels in s (all characters in s are consonants), so we return "lYmpH".

 

Constraints:

  • 1 <= s.length <= 105
  • s consists only of letters of the English alphabet in uppercase and lowercase.

Approach Overview

Problem Overview: You are given a string and need to sort only the vowels (a, e, i, o, u in both lowercase and uppercase). Consonants must stay in their original positions. The final string should have vowels appearing in sorted ASCII order while every non-vowel character remains unchanged.

Approach 1: Two-Pass Extraction and Sorting (O(n + k log k) time, O(k) space)

Scan the string once and collect all vowel characters into a separate list. The number of vowels is k. Sort this list using a standard sorting algorithm, which costs O(k log k). In a second pass over the string, whenever you encounter a vowel, replace it with the next element from the sorted list.

The key insight: consonants never move, so you only manipulate the subset of vowel characters. The first pass isolates the data that needs ordering, and the second pass reinserts it while preserving original positions of non-vowels. This approach is simple to reason about and works well with languages that provide efficient built-in sort utilities. It heavily relies on basic string traversal and sorting.

Approach 2: In-Place Modification with Two Pointers (O(n + k log k) time, O(k) space)

Convert the string into a mutable character array. First gather and sort the vowels exactly as in the previous approach. Instead of rebuilding a new string, maintain a pointer that walks through the sorted vowel list while scanning the original array. Whenever a vowel position appears, overwrite it with the next sorted vowel.

The "two pointers" idea comes from tracking two sequences simultaneously: one pointer scans the string while another consumes the sorted vowel array. This avoids building an entirely new result string and modifies the character array directly. It is still dominated by the vowel sort step (O(k log k)) but keeps the code tight and memory usage predictable. This pattern commonly appears in problems involving two pointers and selective character replacement.

Recommended for interviews: The two-pass extraction and sorting approach is the clearest solution and usually what interviewers expect first. It demonstrates that you can isolate relevant elements, apply sorting, and rebuild the result efficiently. The in-place pointer variant shows stronger control over memory and iteration patterns, which signals deeper comfort with string manipulation.

Approach 1: Using Two-Pass and Sorting

This approach consists of two main parts: identifying and sorting vowels, and reconstructing the string with sorted vowels while keeping consonants in their original places. In the first pass, we traverse the string to collect all the vowels and simultaneously record their indices. Then we sort the collected vowels. In the second pass, we construct the new string by placing the vowels back in their recorded positions in sorted order, while consonants are directly copied from the original string.

This C implementation defines a helper function isVowel() to check if a character is a vowel. Vowels are collected in an array, and their indices are stored separately. After sorting the vowels, the result string is constructed by keeping consonants in place and inserting sorted vowels at their respective original indices.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m^2), where n is the length of the string and m is the number of vowels (due to sorting, which isn't optimized here to O(m log m)).
Space Complexity: O(n), where n is the length of the string for storing the result and vowels.

Try this approach in the editor →

Approach 2: In-Place Modification with Two Pointers

This in-place approach is optimized beyond the two-pass method using a two-pointer technique tailored for scenarios where vowels need to be sorted and replaced directly in the original string buffer. Instead of additional space for vowel storage and indexing, we identify vowels and simultaneously allow swapping to form sorted order based on ASCII comparison efficiently.

This C solution adopts a two-pointer approach for in-place sorting. The function iterates with two pointers, left and right, moving toward each other. It only swaps when conditions meet that vowels appear out of order according to ASCII values, making it simple and reducing additional space.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) for in-place sorting of vowels.
Space Complexity: O(1) due to in-place modification.

Try this approach in the editor →

Approach 3: Sorting

First, we store all the vowels in the string into an array or list vs, then we sort vs.

Next, we traverse the string s, keeping the consonants unchanged. If it is a vowel, we replace it in order with the letters in the vs array.

The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the string s.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Two-Pass and Sorting

Time Complexity: O(n + m^2), where n is the length of the string and m is the number of vowels (due to sorting, which isn't optimized here to O(m log m)).
Space Complexity: O(n), where n is the length of the string for storing the result and vowels.

In-Place Modification with Two Pointers

Time Complexity: O(n^2) for in-place sorting of vowels.
Space Complexity: O(1) due to in-place modification.

Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pass Extraction and SortingO(n + k log k)O(k)Best general solution. Clear logic and easy to implement with built-in sorting.
In-Place Modification with Two PointersO(n + k log k)O(k)When you want to avoid constructing a new string and update characters directly.

Video Solution

2785. Sort Vowels in a String | 2 ways | Counting Sort • Aryan Mittal • 2,327 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sort Vowels in a String easy or hard?
LeetCode classifies this problem as Medium. The logic is straightforward once you recognize that only vowels need to be reordered. The challenge is identifying the clean two-pass pattern and handling uppercase and lowercase vowels correctly.
Sort Vowels in a String Python/Java solution
In Python or Java, iterate through the string, store vowels in a list, and sort it using the language's built-in sort function. Then iterate again and replace each vowel with the next element from the sorted list. The implementation stays under O(n + k log k) time with O(k) extra space.
How to solve Sort Vowels in a String in O(n)?
An O(n) solution is theoretically possible by using counting sort because the vowel alphabet is small and fixed (10 possible characters including case). Count each vowel frequency, then refill vowel positions in sorted order. This avoids comparison-based sorting and keeps overall complexity linear.
What is the best approach for Sort Vowels in a String?
The most practical solution uses a two-pass strategy: first collect all vowels from the string, then sort them, and finally place them back into their original vowel positions. This runs in O(n + k log k) time where k is the number of vowels. The approach keeps consonants fixed while only reordering the vowel subset.
Is Sort Vowels in a String asked at Google/Amazon/Meta?
String manipulation and selective sorting problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, similar patterns involving character filtering, sorting subsets, and reconstructing strings are common interview exercises.
What data structure is used in Sort Vowels in a String?
The main data structures are a list or array to store extracted vowels and a set or lookup table to quickly check if a character is a vowel. Sorting is applied to the vowel array, and a pointer or index is used to place them back into the string.
What is the time complexity of Sort Vowels in a String?
The typical solution runs in O(n + k log k) time. The string is scanned once to collect vowels (O(n)), then the vowels are sorted (O(k log k)), and finally another pass replaces vowel positions (O(n)). Space complexity is O(k) to store the vowel list.

Ready to solve this problem?

Practice Sort Vowels in a String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Reverse Vowels of a String