Можно ли найти количество отличающихся символов в двух строках, не перебирая все символы?

Упорядочить? Как минимум, если символ меньше минимального - сравнивать больше не нужно

Хотя лучше использовать таблицы символов

А если номер элемента важен, тогда только попарное сравнение

Levenshtein distance ищешь ты скорее всего.

PS: и моя древняя поделка на туже тему: https://github.com/dim13/lavenshtein

Задачка O(N) однозначно. Я уверен - можно извернуться и ускорится x2/4/8 (но не больше) особенно если строки aligned (бежать по 4-8 байт, вычитать как int/long, и считать число ненулевых байтов в результате). Здесь есть специалисты которые могут подсказать конкретику, slovazap в частности - что касается x86 asm я с ним тягаться даже пытаться не буду ;)

А это случайно не задачка с собеседований?

Нет. Мне самому в голову взбрело.

Спасибо за информацию.

Ксорнуть две эти строки, потом посчитать количество «0x00». Это если задача о том, чтобы узнать, какое количество символов на тех же позициях в первой и во второй строке совпадают

Да. Мне XOR приходил в голову. По идее, это будет быстрее простого перебора.

Ну вообще-то XOR и последующее сравнение результатов с нулём есть попарное сравнение, я бы не принял такое решение. Была подобная задача с собеседований, где нужно было какую-то контрольную сумму, но точно не помню, и XOR там тоже фигурировал.

в питоне difflib

ты не написал главное - язык. на скриптовых языках типа js/python того же левенштейна не имеет смысла реализовывать, потому как потребление ресурсов на порядки вырастает. на больших текстах может вешать комп

это, кстати, главный аргумент в пользу бесполезности изучения примитивных алгоритмов на скриптовых языках (реализовывать никогда не придется). в питоне много либ, которые нативно реализуют, например, AES-шифрование и у таких либ как правило slow в названии

что же касается твоей задачи, то можно:

➜ ipython                   
Python 3.10.2 (main, Jan 15 2022, 19:56:27) [GCC 11.1.0]
Type 'copyright', 'credits' or 'license' for more information
IPython 8.0.1 -- An enhanced Interactive Python. Type '?' for help.

In [1]: from collections import Counter

In [2]: c1 = Counter("cat")

In [3]: c2 = Counter("rat")

In [4]: c1 - c2
Out[4]: Counter({'c': 1})

In [5]: 

Там создаются два ассоциативных массива, где ключ это символ, а значение сколько раз он встречается в тексте.

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