Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Consonants must stay at their original indices, so only the multiset of vowels and the positions reserved for them matter. Sorting the vowel characters and filling those positions left to right produces the required result.

Approach

Extract uppercase and lowercase vowels while preserving all other characters. Python marks vowel positions with *, which cannot occur in the letter-only input. Sort the extracted vowels by character order, where uppercase vowels precede lowercase ones, and put them back into vowel positions in that order. Join the characters. Case is preserved rather than normalized, and a string without vowels remains unchanged.

class Solution:
    def sortVowels(self, s: str) -> str:
        n = len(s)
        v = []
        s = list(s)

        for i in range(n):
            if s[i] in 'aeiouAEIOU':
                v.append(s[i])
                s[i] = '*'

        v.sort()
        j = 0

        for i in range(n):
            if s[i] == '*':
                s[i] = v[j]
                j += 1

        return "".join(s)

Complexity analysis

Let n = s.length and v be the number of vowels. Time: O(n + v log v). Auxiliary space: O(n + v) for character and vowel arrays.