Тут написано "Complexity: Unspecified, but generally up to linear in the new string length."

И действительно:

for (int i = k - 1; i > 1; --i)
    s = (char)('a' + i) + s;
for (int i = 0; i <= n; ++i)
    s1 = s1 + (char)('a' + (i % 2));

В случае строк посмотрим на оператор +:

template<typename _CharT, typename _Traits, typename _Alloc>
  basic_string<_CharT, _Traits, _Alloc>
  operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
  {
    basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
    __str.append(__rhs);
    return __str;
  }

И на оператор +=:

basic_string&
operator+=(const basic_string& __str)
  { return this->append(__str); }

То есть ваш код работал за квадрат, так как создавался объект на основе первой строки, затем уже к нему добавлялась вторая строка. В случае строк лучше делать +=. Так как не создаются объекты, если они нам не нужны, а работает, как push_back в массиве.

Странно пенять на операцию "+=", которой в вашем коде вообще нет. Эта операция работает быстро. У вас же каждый раз выполняется простое присваиваение s = s+один_символ. Это, конечно, работает долго.

Всю жизнь строки складывал так же, как ты. Спасибо за подсказку, больше так делать не буду :3

Понятно же, что s = t + s будет работать за квадрат. Нельзя просто так взять и дописать элементы спереди. Если уж очень надо, то deque<char> какой-нибудь поможет, наверно.