Первый создает промежуточную строку (которая будет назначена на s после операции +), а вторая - нет (зависит от емкости строки).
Сложность в худшем случае одинакова в обоих случаях, в лучшем случае это просто копирование новой строки для второго случая с полной копией обеих строк для первого случая (+ выделение памяти и освобождение).
Тот факт, что ваш get TLE (Time Limit Exceeded), вероятно, из-за этого наихудшего случая все время копирует огромные строки, а не просто добавляет что-то к существующей (без перераспределения). Как и вектор, в string должна быть некоторая эвристика, чтобы заранее получить достаточную пропускную способность.
Как сказал @Slava, этот пример должен быть написан по-другому, я полагаю, что реальный код отличается.