1. Идея

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

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

Тогда задача сводится к простому проходу по строке слева направо и подсчёту таких позиций.

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

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

Для позиции i символ s[i] является началом слова, если выполняются два условия:

• s[i] != ' '
• и при этом:
  • i == 0, то есть это первый символ строки,
  • или s[i - 1] == ' ', то есть перед ним пробел.

Именно такие символы дают количество слов.

Примеры:

• строка "a"

  • символ a стоит в начале строки и не является пробелом, значит это начало слова;
  • ответ: 1.

• строка "ab cd"

  • a — начало первого слова;
  • c — после пробела, значит начало второго слова;
  • ответ: 2.

• строка "one two"

  • o — начало первого слова;
  • t — первый непробельный символ после нескольких пробелов, значит начало второго слова;
  • ответ: 2.

3. Алгоритм

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

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

Каждое слово имеет ровно один первый символ.

Этот первый символ обязательно:

• не равен пробелу;
• либо стоит в начале строки, либо идёт сразу после пробела.

Значит, каждое слово будет учтено ровно один раз.

С другой стороны, если символ удовлетворяет этим условиям, то он действительно является первым символом некоторого непрерывного фрагмента непробельных символов, то есть началом слова.

Итак:

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

Следовательно, алгоритм правильно находит количество слов в строке.

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)