Перестановка с разными элементами в каждой позиции

у меня есть строка, я хочу из неё составить 2 перестановки, у которых будут различные элементы в каждой позиции.

Вот что я попытался сделать:

#include "bits/stdc++.h"

#define ll long long

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string A;
    cin >> A;

    int n = A.size();

    map<char, int> freq;

    for (int i = 0; i < n; i++) {
        freq[A[i]]++;
    }

    for (auto p : freq) {
        if (p.second > n / 2) {
            cout << "IMPOSSIBLE" << '\n';
            return 0;
        }
    }

    string B = A, C;

    while (n != C.size()) {
        C.clear();
        next_permutation(B.begin(), B.end());

        vector<bool> used(n);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!used[j] && B[i] != A[j]) {
                    C += A[j];
                    used[j] = 1;
                    break;
                }
            }
        }
    }

    cout << B << '\n';
    cout << C << '\n';

    return 0;
}

Однако оно на некоторых строках очень долгое. Ограничение длины строки A 1000 символов.