Представьте, что вам нужно перебрать много случайных перестановок строки и выполнить какую-то быструю проверку для каждой. Проверка настолько быстрая, что узким местом в вашем решении становится шаффл. Для простоты, в сниппете я ускорил проверку до no-op и добавил вывод финальной строки.

#include <bits/stdc++.h>
using namespace std;

#define ITER 10000

int main() {
    string s; cin >> s;
    for (int i = 0; i < ITER; ++i) {
        random_shuffle(s.begin(), s.end());
        // do_something(s);
    }
    cout << s << '\n';
}

Бенчмаркать будем на случайной строке длины $$$2 \cdot 10^5$$$. Кстати, на Unix системах получить такую строку очень просто.

tr -dc '[:alnum:]' < /dev/urandom | head -c 200000 > stroka.txt