Разбор задачи «Различия по позициям»

1. Идея

Нужно сравнить две строки s и t одинаковой длины посимвольно и посчитать, в скольких позициях символы не совпадают.

Самая прямая идея: пройти по всем индексам от 0 до |s| - 1 и каждый раз проверять, равны ли s[i] и t[i]. Если нет — увеличивать счётчик.

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

1. По условию строки имеют одинаковую длину, значит можно спокойно сравнивать символы с одинаковыми индексами.

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

3. Ограничение до 2 * 10^5 символов означает, что нужен линейный алгоритм — один проход по строкам отлично подходит.

3. Алгоритм

1. Считать строки s и t.
2. Завести переменную diff = 0.
3. Для каждого индекса i от 0 до len(s) - 1:
   • если s[i] != t[i], увеличить diff на 1.
4. Вывести diff.

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

Мы рассматриваем каждую позицию ровно один раз.

• Если в позиции i символы одинаковые, эта позиция не должна учитываться.
• Если в позиции i символы разные, она должна увеличить ответ на 1.

Так как алгоритм проверяет все позиции и для каждой принимает именно такое решение, итоговый счётчик diff в точности равен количеству отличающихся позиций.

5. Сложность

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

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

6. Код на C++17

#include <iostream>
#include <string>
using namespace std;

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

    int diff = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] != t[i]) {
            diff++;
        }
    }

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

7. Код на Python 3

s = input()
t = input()

diff = 0
for i in range(len(s)):
    if s[i] != t[i]:
        diff += 1

print(diff)