Разбор задачи «Гласные вверх, согласные вниз»

1. Идея

Нужно пройти по строке посимвольно и для каждой буквы определить:

• если это гласная a, e, i, o, u, то в ответ нужно записать её в верхнем регистре;
• иначе это согласная, и её нужно записать в нижнем регистре.

Так как во входе могут быть и большие, и маленькие буквы, удобно сначала привести текущий символ к нижнему регистру, а потом уже проверять, гласный он или нет.

2. Наблюдения

1. Нас интересует не исходный регистр буквы, а только сама буква. Например, A и a должны обрабатываться одинаково.

2. Поэтому для каждого символа удобно сделать low = lowercase(c).

3. После этого:

   • если low входит в набор a, e, i, o, u, то добавляем uppercase(low);
   • иначе добавляем low.

4. Строка может быть длиной до 2 * 10^5, поэтому решение должно работать за линейное время, то есть за O(n).

3. Алгоритм

1. Считать строку s.
2. Создать пустую строку ответа или список символов.
3. Для каждого символа c в s:
   • перевести его в нижний регистр;
   • проверить, является ли он одной из гласных;
   • если да, добавить в ответ заглавную версию этой буквы;
   • иначе добавить строчную версию.
4. Вывести результат.

4. Почему это работает

Рассмотрим любой символ строки.

• Сначала мы переводим его в нижний регистр. Теперь буквы A и a, E и e и так далее становятся одинаковыми с точки зрения проверки.
• Если полученная буква — одна из гласных a, e, i, o, u, по условию она должна стать заглавной. Именно это и делает алгоритм.
• Если это не гласная, значит это согласная латинская буква. По условию она должна стать строчной. Алгоритм добавляет как раз строчную форму.

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

5. Сложность

Пусть длина строки равна n.

• Время: O(n), потому что каждый символ обрабатывается один раз.
• Память: O(n), так как нужно сохранить строку ответа.

6. Код на C++17

#include <iostream>
#include <string>
#include <cctype>

using namespace std;

int main() {
    string s;
    cin >> s;

    string ans;
    ans.reserve(s.size());

    for (char c : s) {
        char low = (char)tolower((unsigned char)c);
        if (low == 'a' || low == 'e' || low == 'i' || low == 'o' || low == 'u') {
            ans += (char)toupper((unsigned char)low);
        } else {
            ans += low;
        }
    }

    cout << ans << "\n";
    return 0;
}

7. Код на Python 3

s = input()

vowels = {'a', 'e', 'i', 'o', 'u'}
result = []

for c in s:
    low = c.lower()
    if low in vowels:
        result.append(low.upper())
    else:
        result.append(low)

print(''.join(result))