Каким образом компилятор Python оптимизирует операции сложения строк: в каких случаях запись `s = s + "next"` приведёт к выделению новой памяти и копированию O(N), а в каких CPython выполнит оптимизацию in-place O(1)?

CPython иногда переиспользует буфер строки при присваивании результата конкатенации той же локальной переменной. Но это оптимизация реализации, а не гарантированное O(1) для s = s + "next".

Специализированный путь проверяет обычные строки и последующий STORE_FAST. Переиспользование требует отсутствия других владельцев и других ограничений, например интернирования или уже вычисленного хеша; расширение внутреннего представления также мешает. Даже допустимый resize может переместить буфер и скопировать O(N) символов. При удачном расширении на месте копируется лишь добавка фиксированной длины. Дополнительная ссылка, например сохранение промежуточных строк в списке, лишает этой возможности. Для большого числа фрагментов надёжнее оценивать ''.join(parts) по суммарной длине, не опираясь на случайное поведение allocator.

Источник: raw.githubusercontent.com, raw.githubusercontent.com.