1. Идея

Нужно посчитать количество слов в строке.

По условию слово — это максимальная последовательность символов, которые не являются пробелами. Значит, каждое слово начинается в некоторой позиции, где:

• текущий символ не пробел;
• либо это первый символ строки, либо перед ним стоит пробел.

Если пройти по строке слева направо и посчитать все такие позиции, то получим точное число слов.

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

Рассмотрим, когда именно начинается новое слово.

Например, в строке hello world:

• первые два символа — пробелы, слова не начинаются;
• символ h не пробел, а перед ним пробел — значит, это начало слова;
• дальше буквы e, l, l, o не являются началом нового слова, потому что перед ними не пробел;
• после нескольких пробелов символ w снова не пробел, а перед ним пробел — это начало второго слова.

Значит, слово соответствует не каждому непробельному символу, а только первому символу блока непробельных символов.

Это удобно проверять условием:

• s[i] != ' '
• и одновременно (i == 0 или s[i - 1] == ' ')

Если оба условия выполнены, увеличиваем ответ.

3. Алгоритм

1. Считать всю строку целиком.
2. Завести переменную count = 0.
3. Пройти по всем позициям строки i от 0 до len(s) - 1.
4. Если:
   • s[i] не равен пробелу,
   • и при этом i == 0 или s[i - 1] равен пробелу, то увеличить count на 1.
5. Вывести count.

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

Докажем, что алгоритм считает слова правильно.

Каждое слово — это максимальная подряд идущая группа непробельных символов. У такой группы есть ровно один первый символ.

Для первого символа слова верно:

• он не пробел;
• перед ним либо конец строки слева, либо пробел.

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

Теперь покажем, что лишнего он не считает:

• если символ находится внутри слова, то перед ним стоит не пробел, поэтому условие начала слова не выполнится;
• если символ — пробел, он тоже не будет посчитан.

Следовательно:

• каждое слово учитывается ровно один раз;
• ничего лишнего не учитывается.

Значит, итоговое значение count равно количеству слов в строке.

5. Сложность

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

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

6. Код на C++17

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    getline(cin, s);

    int count = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] != ' ' && (i == 0 || s[i - 1] == ' ')) {
            count++;
        }
    }

    cout << count << '\n';
    return 0;
}

7. Код на Python 3

s = input()

count = 0
for i in range(len(s)):
    if s[i] != ' ' and (i == 0 or s[i - 1] == ' '):
        count += 1

print(count)