Задача с собеседования в Zoho

Даны две строки: s и goal. Верните true, если можно поменять местами два символа в строке s так, чтобы в результате она стала равна строке goal. В противном случае верните false.

Под обменом символов понимается выбор двух индексов i и j (индексация начинается с 0) таких, что i != j, и перестановка символов s[i] и s[j] местами.
Например, обмен символов по индексам 0 и 2 в "abcd" даёт "cbad".

Пример 1:
Input: s = "ab", goal = "ba"
Output: true
Explanation: Вы можете поменять местами s[0] = "a" and s[1] = "b", чтобы получить "ba", что равно goal.

Пример 2:
Input: s = "ab", goal = "ab"
Output: false
Explanation: Единственные символы, которые можно поменять местами - это s[0] = "a" and s[1] = "b", в результате чего "ba" != goal.

Пример 3:
Input: s = "aa", goal = "aa"
Output: true
Explanation: Вы можете поменять местами s[0] = "a" and s[1] = "a", чтобы получить "aa", что равно goal.

Ограничения:
1 <= s.length, goal.length <= 2 * 10⁴
s и goal состоят из строчных букв.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Итак, нам нужно обменять ровно две позиции строки s, в которых s и goal различаются; остальные позиции должны совпадать сразу.
=> различий между строками должно быть либо 2 (так как один обмен исправляет только два различия), либо 0 (то есть строки уже эквивалентны).

Обрабатываем следующие случаи:
- Если длина s и goal различается:
False, так как обмен символов не изменит разницу в кол-ве символов.

- Если строки уже эквивалентны:
Необходимо наличие повторяющегося символа (проверяем, есть ли он, через сравнение строки со множеством), так как только обмен одинаковых символов не изменит строку s, уже равную goal. В этом случае возвращается true, иначе - false.

- Если строки разные:
Ищем две различающиеся позиции и проверяем, можно ли поменять два символа ровно одним обменом, чтобы получить goal.

diff - массив индексов, где s[i] != goal[i].

Проходим по строке s:
Если символ по текущему индексу в s отличается от символа по текущему индексу в goal:
- добавляем индекс в diff.

Если кол-во различающихся индексов становится больше 2:
- False, так как одного обмена, затрагивающего две позиции, недостаточно для исправления различий.

Если не нашли 2 различающихся индекса (len(diff) == 1):
- False, так как обмен меняет две позиции и не может покрыть одну позицию без создания нового различия в другой позиции.

Если нашли ровно 2 различающихся индекса:
- проверяем, можем ли перекрёстно поменять символы местами, чтобы получить goal.

Сложность
O(n) - по времени (в худшем случае (когда строки равны) делаем два линейных прохода)
O(1) - по памяти (diff хранит не более трёх индексов (на третьем - выход), set(s) хранит только уникальные символы, т.е. не более 26 эл-в)

Код
class Solution:
def buddyStrings(self, s: str, goal: str) -> bool:
if len(s) != len(goal):
return False

if s == goal:
return len(set(s)) < len(s)

diff = []

for i in range(len(s)):
if s[i] != goal[i]:
diff.append(i)

if len(diff) > 2:
return False

if len(diff) != 2:
return False

i, j = diff

return s[i] == goal[j] and s[j] == goal[i]

Подписаться: @algoses