利用全排列函数加vector数组,开十个vector,存a到i字母出现的位置,最后每个vector再push_back(字符串长度加一)作为结束标志。
由于同一字符串只算一个,只要每种情况下有一种字符串就加一,然后全排列函数
#include<bits/stdc++.h>
using namespace std;
int id[10];
vector<int> vt[10];
char s[3002];
int main()
{
scanf("%s",s+1);
int n=strlen(s+1);
for(int i=1;i<=n;i++)
vt[s[i]-'a'].push_back(i);
for(int i=0;i<9;i++)
id[i]=i,vt[i].push_back(n+1);
int ans=0;
do{
int p=0;
for(int i=0;i<9;i++)
{
p=*upper_bound(vt[id[i]].begin(),vt[id[i]].end(),p);
if(p==n+1)
break;
}
if(p<n+1)
ans++;
}while(next_permutation(id,id+9));
printf("%d\n",ans);
return 0;
}