题解 | 游游的字符重排

DFS枚举并回溯

#include <iostream>
#include<string>
#include<vector>
using namespace std;

int cnt=0;
vector<int>freq;
int n;
void back(int pos,char prev){
    if(pos==n){
        cnt++;
        return ;
    }
    for(char c='a';c<='z';c++){
        int idx=c-'a';
        if(freq[idx]>0&&c!=prev){
            freq[idx]--;
            back(pos+1,c);
            freq[idx]++;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin>>s;
    n=s.size();
    freq.resize(26,0);
    for(char c:s){
        freq[c-'a']++;
    }
    back(0,-1);
    cout<<cnt<<endl;
    return 0;
}