#2785 Sort Vowels in a String - Solution

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.

In #2785 Sort Vowels in a String, the goal is to reorder only the vowels in a string while keeping all consonants and their positions unchanged. A common strategy is to perform the task in two passes. First, iterate through the string and collect all characters that belong to the vowel set (a, e, i, o, u in both lowercase and uppercase). Store these vowels in a separate list.

Next, sort the collected vowels using a standard sorting algorithm. After sorting, traverse the original string again and replace each vowel position with the next element from the sorted list. This ensures that consonants remain untouched while vowels appear in sorted order.

This approach works efficiently because only the vowel subset is sorted rather than the entire string. If n is the string length and k is the number of vowels, the main cost comes from sorting the vowels. The algorithm is straightforward to implement and leverages simple data structures like arrays or lists.

Approach	Time Complexity	Space Complexity
Collect vowels, sort, and replace	O(n + k log k)	O(k)

Solutions (12)

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.

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.

C C++Java Python C#JavaScript

1using System;
2using System.Collections.Generic;
3
4class SortVowelsInString {
5    static bool IsVowel(char c) {
6        c = Char.ToLower(c);
7        return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
8    }
9
10    public static string SortVowelsInStringMethod(string s) {
11        List<char> vowels = new List<char>();
12        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));
    }
}

Explanation

This C# approach stores vowels in a List<char> and sorts them with List.Sort(). It uses a character array to efficiently manage in-place character replacements and constructs the final output using the updated array.

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.

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

C C++Java Python C#JavaScript


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));
    }
}