#2785

Medium

LeetCode Problem Workspace

Sort Vowels in a String

Sort Vowels in a String requires identifying vowels in a string and rearranging them in ascending order while keeping consonants fixed.

string sorting

Problem Statement

Given a 0-indexed string s, create a new string t where all vowels in s are sorted in ascending ASCII order, and consonants remain in their original positions. Vowels include 'a', 'e', 'i', 'o', and 'u', and both uppercase and lowercase forms should be handled.

Return the resulting string t after sorting the vowels. For example, for s = 'lEetcOde', the vowels 'E', 'O', and 'e' are sorted to produce 'lEOtcede'. If s contains no vowels, the string remains unchanged. The solution must handle strings up to length 105 efficiently.

Examples

Example 1

Input: s = "lEetcOde"

Output: "lEOtcede"

'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"

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.

Solution Approach

Collect and Sort Vowels

Traverse the string and collect all vowels into a list, preserving their order of appearance. Sort this list using ASCII values to ensure correct uppercase and lowercase ordering.

Replace Vowels in Original String

Iterate through the original string again, replacing each vowel with the next element from the sorted vowels list while leaving consonants untouched. This maintains consonant positions and solves the string plus sorting pattern.

Return the Resulting String

After all vowels are replaced in order, join the characters to form the final string. This approach ensures O(N) time complexity and minimal extra space, directly addressing the problem's constraints.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

Time complexity is O(N) for traversing the string and sorting at most N vowels. Space complexity is O(1) extra if in-place replacement is allowed, or O(V) for storing V vowels.

What Interviewers Usually Probe

Check if candidate correctly identifies vowels and handles both cases.
Listen for discussion about maintaining consonant positions while sorting vowels.
Watch for explanations of ASCII-based sorting versus case-insensitive sorting.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle uppercase vowels separately, leading to incorrect ASCII order.
Modifying consonant positions while inserting sorted vowels.
Assuming all strings contain vowels, causing errors when vowel list is empty.

Follow-up variants

Sort only lowercase vowels while ignoring uppercase letters.
Sort vowels in reverse ASCII order while keeping consonants fixed.
Sort vowels according to frequency of appearance instead of ASCII order.

FAQ

What is the main pattern used in Sort Vowels in a String?

The primary pattern is String plus Sorting, where only vowels are extracted, sorted, and reinserted while keeping consonants fixed.

How do I handle uppercase and lowercase vowels?

Treat uppercase and lowercase vowels according to their ASCII values during sorting to preserve correct order.

What if the string has no vowels?

If there are no vowels, return the original string unchanged as there are no elements to sort.

Can I solve this in-place to save space?

Yes, you can replace vowels in the original string while traversing it, using only O(V) extra space for vowel storage.

Why is sorting vowels without moving consonants tricky?

Because inserting sorted vowels incorrectly can shift consonants, violating the problem requirement of keeping consonant positions fixed.

terminal

Solution

Solution 1: Sorting

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

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def sortVowels(self, s: str) -> str:
        vs = [c for c in s if c.lower() in "aeiou"]
        vs.sort()
        cs = list(s)
        j = 0
        for i, c in enumerate(cs):
            if c.lower() in "aeiou":
                cs[i] = vs[j]
                j += 1
        return "".join(cs)

Continue Practicing

#2840 check if strings can be made equal with operations ii #2933 high access employees #3016 minimum number of pushes to type word ii