2785. Sort Vowels in a String - Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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 <= 10⁵
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.

Python

def is_vowel(c):
    return c.lower() in 'aeiou'

def sort_vowels_in_string(s):
    vowels = [c for c in s if is_vowel(c)]
    vowels.sort()
    result = list(s)
    v_index = 0
    for i in range(len(result)):
        if is_vowel(result[i]):
            result[i] = vowels[v_index]
            v_index += 1
    return ''.join(result)

# Test
s = "lEetcOde"
print(sort_vowels_in_string(s))

Java

import java.util.*;

public class SortVowels {
    public static boolean isVowel(char c) {
        c = Character.toLowerCase(c);
        return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
    }

    public static String sortVowelsInString(String s) {
        List<Character> vowels = new ArrayList<>();
        for (char c : s.toCharArray()) {
            if (isVowel(c)) {
                vowels.add(c);
            }
        }
        Collections.sort(vowels);

        StringBuilder result = new StringBuilder(s);
        int vowelIndex = 0;
        for (int i = 0; i < s.length(); i++) {
            if (isVowel(s.charAt(i))) {
                result.setCharAt(i, vowels.get(vowelIndex++));
            }
        }
        return result.toString();
    }

    public static void main(String[] args) {
        String test = "lEetcOde";
        System.out.println(sortVowelsInString(test));
    }
}

C++

#include <iostream>
#include <string>
#include <algorithm>

bool isVowel(char c) {
    c = tolower(c);
    return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}

std::string sortVowelsInString(std::string s) {
    std::string vowels;
    for (char c : s) {
        if (isVowel(c)) {
            vowels += c;
        }
    }
    std::sort(vowels.begin(), vowels.end());

    int vowelIndex = 0;
    for (char &c : s) {
        if (isVowel(c)) {
            c = vowels[vowelIndex++];
        }
    }
    return s;
}

int main() {
    std::string test = "lEetcOde";
    std::cout << sortVowelsInString(test) << std::endl;
    return 0;
}

JavaScript

function isVowel(c) {
    return 'aeiouAEIOU'.includes(c);
}

function sortVowelsInString(s) {
    const vowels = [...s].filter(isVowel);
    vowels.sort();
    let vowelIndex = 0;
    return Array.from(s).map(c => isVowel(c) ? vowels[vowelIndex++] : c).join('');
}

// Test
const s = "lEetcOde";
console.log(sortVowelsInString(s));

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int isVowel(char c) {
    c = tolower(c);
    return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}

void sortVowels(char *vowels, int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = i+1; j < n; j++) {
            if (vowels[i] > vowels[j]) {
                char temp = vowels[i];
                vowels[i] = vowels[j];
                vowels[j] = temp;
            }
        }
    }
}

char* sortVowelsInString(const char *s) {
    int len = strlen(s);
    char *result = (char *)malloc((len + 1) * sizeof(char));
    char vowels[100000];
    int indices[100000];
    int vowelCount = 0;

    for (int i = 0; i < len; i++) {
        result[i] = s[i];
        if (isVowel(s[i])) {
            vowels[vowelCount] = s[i];
            indices[vowelCount++] = i;
        }
    }
    sortVowels(vowels, vowelCount);

    for (int i = 0; i < vowelCount; i++) {
        result[indices[i]] = vowels[i];
    }
    result[len] = '\0';
    return result;
}

int main() {
    const char *test = "lEetcOde";
    char *sorted = sortVowelsInString(test);
    printf("%s\n", sorted);
    free(sorted);
    return 0;
}

using System;
using System.Collections.Generic;

class SortVowelsInString {
    static bool IsVowel(char c) {
        c = Char.ToLower(c);
        return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
    }

    public static string SortVowelsInStringMethod(string s) {
        List<char> vowels = new List<char>();
        foreach (char c in s) {
            if (IsVowel(c)) {
                vowels.Add(c);
            }
        }
        vowels.Sort();

        char[] result = s.ToCharArray();
        int vowelIndex = 0;
        for (int i = 0; i < result.Length; i++) {
            if (IsVowel(result[i])) {
                result[i] = vowels[vowelIndex++];
            }
        }
        return new string(result);
    }

    static void Main() {
        string test = "lEetcOde";
        Console.WriteLine(SortVowelsInStringMethod(test));
    }
}

This Python implementation uses list comprehensions to collect vowels and the list's sort method for sorting them. The function sort_vowels_in_string reconstructs the string using a list for efficient character assignment, and finally joins the list into a string to return the result.

Complexity

Time Complexity: O(n + m log m), where n is the length of the string and m is the number of vowels (for sorting).
Space Complexity: O(m), for storing 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.

Python

def is_vowel(c):
    return c.lower() in 'aeiou'

def sort_vowels_in_place(s):
    s = list(s)
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not is_vowel(s[left]):
            left += 1
        while left < right and not is_vowel(s[right]):
            right -= 1
        if left < right and s[left] > s[right]:
            s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
    return ''.join(s)

# Test
s = "lEetcOde"
print(sort_vowels_in_place(s))

Java

public class SortVowelsInPlace {
    public static boolean isVowel(char c) {
        c = Character.toLowerCase(c);
        return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
    }

    public static String sortVowelsInPlace(String s) {
        char[] chars = s.toCharArray();
        int left = 0, right = chars.length - 1;
        while (left < right) {
            while (left < right && !isVowel(chars[left])) left++;
            while (left < right && !isVowel(chars[right])) right--;
            if (left < right && chars[left] > chars[right]) {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
            }
            left++;
            right--;
        }
        return new String(chars);
    }

    public static void main(String[] args) {
        String test = "lEetcOde";
        System.out.println(sortVowelsInPlace(test));
    }
}

C++

#include <iostream>
#include <string>

bool isVowel(char c) {
    c = tolower(c);
    return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}

void sortVowelsInPlace(std::string &s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        while (left < right && !isVowel(s[left])) left++;
        while (left < right && !isVowel(s[right])) right--;
        if (left < right && s[left] > s[right]) {
            std::swap(s[left], s[right]);
        }
        left++;
        right--;
    }
}

int main() {
    std::string test = "lEetcOde";
    sortVowelsInPlace(test);
    std::cout << test << std::endl;
    return 0;
}

JavaScript

function isVowel(c) {
    return 'aeiouAEIOU'.includes(c);
}

function sortVowelsInPlace(s) {
    const chars = s.split('');
    let left = 0, right = chars.length - 1;
    while (left < right) {
        while (left < right && !isVowel(chars[left])) left++;
        while (left < right && !isVowel(chars[right])) right--;
        if (left < right && chars[left] > chars[right]) {
            [chars[left], chars[right]] = [chars[right], chars[left]];
        }
        left++;
        right--;
    }
    return chars.join('');
}

// Test
const s = "lEetcOde";
console.log(sortVowelsInPlace(s));

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int isVowel(char c) {
    c = tolower(c);
    return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}

void sortVowelsInPlace(char *s) {
    int left = 0, right = strlen(s) - 1;
    char temp;
    while (left < right) {
        while (left < right && !isVowel(s[left])) left++;
        while (left < right && !isVowel(s[right])) right--;
        if (left < right && s[left] > s[right]) { 
            temp = s[left];
            s[left] = s[right];
            s[right] = temp;
        }
        left++;
        right--;
    }
}

int main() {
    char s[] = "lEetcOde";
    sortVowelsInPlace(s);
    printf("%s\n", s);
    return 0;
}

using System;

class SortVowelsInPlace {
    static bool IsVowel(char c) {
        c = Char.ToLower(c);
        return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
    }

    public static string SortVowelsInStringMethod(string str) {
        char[] s = str.ToCharArray();
        int left = 0, right = s.Length - 1;
        while (left < right) {
            while (left < right && !IsVowel(s[left])) left++;
            while (left < right && !IsVowel(s[right])) right--;
            if (left < right && s[left] > s[right]) {
                char temp = s[left];
                s[left] = s[right];
                s[right] = temp;
            }
            left++;
            right--;
        }
        return new string(s);
    }

    static void Main() {
        string test = "lEetcOde";
        Console.WriteLine(SortVowelsInStringMethod(test));
    }
}

This Python solution adopts a two-pointer method to efficiently swap vowels in place to achieve a sorted position, leveraging the list structure for mutable operations directly within the function's scope.

Complexity

Time Complexity: O(n^2) for sorting in place.
Space Complexity: O(1), modified in place.

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.

TypeScript

function sortVowels(s: string): string {
    const vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'];
    const vs = s
        .split('')
        .filter(c => vowels.includes(c))
        .sort();
    const ans: string[] = [];
    let j = 0;
    for (const c of s) {
        ans.push(vowels.includes(c) ? vs[j++] : c);
    }
    return ans.join('');
}

func sortVowels(s string) string {
	cs := []byte(s)
	vs := []byte{}
	for _, c := range cs {
		d := c | 32
		if d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u' {
			vs = append(vs, c)
		}
	}
	sort.Slice(vs, func(i, j int) bool { return vs[i] < vs[j] })
	j := 0
	for i, c := range cs {
		d := c | 32
		if d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u' {
			cs[i] = vs[j]
			j++
		}
	}
	return string(cs)
}

Rust

impl Solution {
    pub fn sort_vowels(s: String) -> String {
        fn is_vowel(c: char) -> bool {
            matches!(c.to_ascii_lowercase(), 'a' | 'e' | 'i' | 'o' | 'u')
        }

        let mut vs: Vec<char> = s.chars().filter(|&c| is_vowel(c)).collect();
        vs.sort_unstable();

        let mut cs: Vec<char> = s.chars().collect();
        let mut j = 0;

        for (i, c) in cs.clone().into_iter().enumerate() {
            if is_vowel(c) {
                cs[i] = vs[j];
                j += 1;
            }
        }

        cs.into_iter().collect()
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Two-Pass and Sorting	Time Complexity: O(n + m log m), where n is the length of the string and m is the number of vowels (for sorting). Space Complexity: O(m), for storing vowels.
In-Place Modification with Two Pointers	Time Complexity: O(n^2) for sorting in place. Space Complexity: O(1), modified in place.
Sorting	–

Complexity analysis

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

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.

Sort Vowels in a String solution and explanation

The problem

Approach overview

Approach 1: Using Two-Pass and Sorting

Approach 2: In-Place Modification with Two Pointers

Approach 3: Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Sort Vowels in a String solution and explanation

The problem

Approach overview

Approach 1: Using Two-Pass and Sorting

Approach 2: In-Place Modification with Two Pointers

Approach 3: Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems