2785. Sort Vowels In String

Problem Statement in English

You’re given a 0-indexed string s that consists of lowercase and uppercase English letters. Your task is to sort the vowels in s in non-decreasing order while keeping the positions of the consonants unchanged.

Approach

This is a straightforward problem. We can extract all the vowels from the string, sort them, and then place them back in the place of every vowel in the original string.

Solution in Python

class Solution:
    def sortVowels(self, s: str) -> str:
        l = list(s)

        v = []
        vowels = ['a', 'e', 'i', 'o', 'u']

        for c in l:
            if c.lower() in vowels:
                v.append(c)

        v.sort()
        p = 0

        for i in range(len(l)):
            if l[i].lower() in vowels:
                l[i] = v[p]
                p += 1

        return ''.join(l)

Complexity

• Time: $O(n \log n)$
  Since we need to sort the vowels, the time complexity is dominated by the sorting step which is $O(m \log m)$ where $m$ is the number of vowels. In the worst case, all characters could be vowels, making it $O(n \log n)$.

• Space: $O(n)$
  We are using extra space to store the vowels, which in the worst case could be all characters in the string, leading to $O(n)$ space complexity.

And we are done.