Задача с собеседования в Zoho

Дана строка s, разверните (изменив порядок на обратный) только все гласные в строке и верните полученную строку.
Гласными являются буквы 'a', 'e', 'i', 'o', и 'u'. Они могут быть как в нижнем, так и в верхнем регистре, а также встречаться более одного раза.

Пример 1:
Input: "IceCreAm"
Output: "AceCreIm"
Explanation:
Гласные в s: ['I', 'e', 'e', 'A']. После разворота гласных s превращается в "AceCreIm".

Пример 2:
Input: s = "leetcode"
Output: "leotcede"

Ограничения:
1 <= s.length <= 3 * 105
s состоит из печатных символов ASCII.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Будем использовать метод двух указателей:
left - индекс первого элемента в списке (после преобразования строки в список)
right - индекс последнего элемента
Гласные храним во множестве для быстрой проверки за O(1).

Пока left меньше right: идём по строке в двух направлениях, проверяя символы, на которые указывают left и right.
Если символ слева - не гласная: сдвигаем левый указатель;
Если символ справа - не гласная: сдвигаем правый указатель;
Если оба символа - гласные: меняем их местами и двигаем оба указателя.

Так проходим по всему списку, пока указатели не встретятся, и в конце возвращаем полученную строку.

Сложность
O(n) - по времени (так как проходим по списку один раз)
O(n) - по памяти (так как создаём список из символов строки)

Код
class Solution:
def reverseVowels(self, s: str) -> str:
s = list(s)
vowels = set("aeiouAEIOU")
left, right = 0, len(s) - 1

while left < right:
if s[left] not in vowels:
left += 1
elif s[right] not in vowels:
right -= 1
else:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1

return "".join(s)

@algoses