10. Reverse Vowels of String

«Хороший программист знает, что делает машина; великий программист предвидит, как она будет это делать».
— Деннис Ритчи

LeetCode 345. Reverse Vowels of a String

Сложность: Easy
Тема: Встречные указатели, строки в Go, селективный обмен in-place, табличные проверки
Ссылки: Теория: Два указателя, Варианты применения, Valid Palindrome

1. Введение и физическая интуиция

Представьте строку как последовательность вагонов в железнодорожном составе: "h e l l o".
Некоторые вагоны — пассажирские (гласные буквы: a, e, i, o, u), другие — грузовые платформы (согласные буквы и знаки препинания).

Задача требует развернуть порядок пассажирских вагонов задом наперед, оставив грузовые платформы строго на своих исходных путях:

• В слове "hello" гласные 'e' и 'o' меняются местами $\implies$ "holle".
• В слове "leetcode" гласные ['e', 'e', 'o', 'e'] превращаются в ['e', 'o', 'e', 'e'] $\implies$ "leotcede".

Используя два встречных указателя, мы скользим с двух концов состава навстречу друг другу:

• Левый указатель ищет первую гласную слева.
• Правый указатель ищет первую гласную справа.
• Обнаружив пару гласных, мы меняем их местами и продолжаем движение к центру состава.

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    A["s = 'leetcode'"]:::entry --> B["b = []byte(s)<br>left = 0, right = len(s)-1"]:::process
    B --> C{"left < right?"}:::warning
    C -->|"Да"| D["Сдвиг left вправо до гласной"]:::process
    D --> E["Сдвиг right влево до гласной"]:::process
    E --> F{"left < right?"}:::warning
    F -->|"Да"| G["b[left], b[right] = b[right], b[left]<br>left++, right--"]:::process
    F -->|"Нет"| H["Выход из цикла"]:::process
    G --> C
    C -->|"Нет"| I["Возвращаем string(b)"]:::success
    H --> I
  

2. Формулировка задачи и вопросы интервьюеру

Дана строка s. Развернуть только гласные буквы в строке и вернуть полученный результат. Гласными буквами считаются 'a', 'e', 'i', 'o', 'u' в строчном и заглавном регистрах ('A', 'E', 'I', 'O', 'U'). Буква 'y' гласной не считается.

Вопросы интервьюеру (Senior-стиль):

1. Каков алфавит входных строк?
   «Стандартные ASCII-символы. Это позволяет использовать мутабельный срез байтов []byte(s) без накладных расходов на []rune(s).»
2. Нужно ли учитывать регистр?
   «Да, заглавные и строчные буквы сохраняют свой регистр при перемещении на новую позицию (например, заглавная 'E' перейдет на место строчной 'o' именно как заглавная 'E').»
3. Что возвращать для пустой строки или строки без гласных?
   «Возвращать исходную строку без изменений.»

3. Разбор подходов

Подход 1: Два прохода со сбором гласных в срез (Наивный)

1. Первый проход: выписать все гласные буквы в отдельный слайс vowels := []byte{}.
2. Второй проход: перезаписать гласные позиции в строке значениями из vowels в обратном порядке.

• Минусы: Два прохода по строке, дополнительная аллокация среза vowels в куче, лишняя работа Garbage Collector.

Подход 2: Встречные указатели на мутабельном буфере (Оптимальный)

Строки в Go неизменяемы (immutable). Мы один раз преобразуем строку в []byte(s) и производим селективный обмен на месте встречными указателями за один проход: $O(N)$ по времени и $O(1)$ вспомогательной памяти (за исключением самого среза байтов).

4. Эталонная реализация на Go

package main

// ReverseVowels разворачивает порядок только гласных букв в строке s.
// Временная сложность: O(N) — каждый байт строки инспектируется не более 2 раз.
// Пространственная сложность: O(N) под мутабельный буфер результата.
func ReverseVowels(s string) string {
    // Строки в Go иммутабельны. Создаем байтовый срез для in-place модификаций
    b := []byte(s)
    left, right := 0, len(b)-1

    for left < right {
        // Пропускаем согласные буквы слева
        for left < right && !isVowel(b[left]) {
            left++
        }
        // Пропускаем согласные буквы справа
        for left < right && !isVowel(b[right]) {
            right--
        }

        // Если оба указателя остановились на гласных и не пересеклись
        if left < right {
            b[left], b[right] = b[right], b[left]
            left++
            right--
        }
    }

    return string(b)
}

// isVowel выполняет O(1) проверку на гласную букву.
// switch компилируется в плоскую jump table или битовую маску без аллокаций.
func isVowel(c byte) bool {
    switch c {
    case 'a', 'e', 'i', 'o', 'u',
        'A', 'E', 'I', 'O', 'U':
        return true
    default:
        return false
    }
}

5. Пошаговая трассировка (Walkthrough)

Рассмотрим слово s = "leetcode" ($len = 8$).

Цикл завершен. Возвращаем строку "leotcede".

6. Mechanical Sympathy: почему switch лучше map

7. Вопросы для собеседования

8. Инварианты и чек-лист самопроверки

• [x] Иммутабельность: исходная строка скопирована в []byte ровно один раз.
• [x] Граничное условие left < right во всех циклах: предотвращает панику выхода за пределы среза.
• [x] Регистронезависимость: проверены все 10 вариантов гласных (5 строчных + 5 заглавных).

Итоги кластера 02 «Два указателя»

Мы завершили детальный разбор всех ключевых задач на паттерн «Два указателя»:

1. Valid Palindrome — встречные указатели на строках с фильтрацией мусора.
2. Two Sum II — математическое сужение пространства поиска в отсортированном срезе.
3. Remove Duplicates — быстрый и медленный указатели (read/write) in-place.
4. 3Sum и 4Sum — сортировка, дедупликация и ранняя отсечка ветвей.
5. Sort Colors — три указателя Дейкстры (голландский флаг).
6. Squares of Sorted Array — встречные указатели с обратным заполнением.
7. Reverse Vowels of String — селективный обмен элементов.

Следующий шаг нашего путешествия — кластер «Скользящее окно» (Sliding Window), где два указателя обретают динамическое состояние и превращают сложные задачи на поиск подмассивов и подстрок в линейные алгоритмы: 1. Теория. Скользящее окно.