Изменения в «LecturesCMC/PythonIntro2022/Homework_SimilarPairs»

Отсортируем слова words

Будем искать максимально возможное k, при котором количество одинаковых префиксов words[i][:k] чётно (часть тестов можно пройти с таким решением)

Заметим, что для этого достаточно просматривать упорядоченные слова, но проверять не words[i][:k], а цепочки одинаковых букв words[i][k-1]: их длины должны быть чётными. В самом деле:

1. Допустим, все префиксы words[i][:k - 1] парные

2. Предположим, что среди префиксов words[i][:k] есть непарные, но все цепочки одинаковых букв в последовательности words[i][k-1] имеют чётную длину.

3. Это значит, что есть такие две цепочки нечётной длины words[i₀][k - 1] … words[i₁][k - 1] и words[i₁ + 1][k - 1] … words[i₂][k - 1], что

   • Буквы в этих цепочках совпадают (поэтому длина words[i₀][k - 1] …  words[i₂][k - 1] чётна)

   • Префиксы words[i₀][:k] … words[i₁][:k] одинаковы, но не равны другим одинаковым префиксам words[i₁ + 1][:k] … words[i₂][:k]

4. Рассмотрим первую тройку i₀, i₁, i₂.

5. Цепочка words[i₀][k - 1] … words[i₁][k - 1] имеет нечётную длину. По предположению (3) это окончание последовательности с одинаковым чуть более коротким префиксом words[i₁][:k - 1]

6. Так как по предположению (1) длина последовательности words[i₁][:k - 1] чётна, в ней должна встретиться минимум ещё одна цепочка words[j₀][k - 1] … words[j₁][k - 1] нечётной длины

7. Получаем противоречие: согласно (5) j₁ должно быть меньше i₀, но в (4) мы рассматривали первую из цепочек нечётной длины.

8. Следовательно, предположение (2) неверно, и если среди префиксов есть непарные, некоторые цепочки будут нечётной длины. ЧТД.