游游的字符重排

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

游游定义一个字符串是“好串”，当且仅当该字符串相邻的字符不相等。例如"$arcaea$"是好串，而"$food$"不是好串。

游游拿到了一个字符串，她可以将该字符串的各个字符顺序随意打乱。她想知道一共可以生产多少种不同的好串？

输入描述：

一个仅包含小写字母的字符串，长度不超过 $10$ 。

输出描述：

好串的数量。

示例1

输入：

aab

输出：

1

说明：

只有"$aba$"这一种好串。

示例2

输入：

arc

输出：

6

示例3

输入：

aaa

输出：

0

解题思路

先对输入字符串进行排序，利用next_permutation枚举所有唯一的全排列（排序可避免重复排列的枚举），对每个排列遍历检查相邻字符是否均不相等，若满足“好串”条件（相邻字符不同）则计数加 $1$ ；最终输出计数结果，该方法因字符串长度 $\le 10$，全排列数量（最多 $10!=3628800$ 次）在时间限制内，能完整枚举所有可能的字符重排情况，精准统计符合要求的不同好串数量。

代码内容

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

typedef long long ll;
typedef pair<ll,ll> pii;
const ll N=1e5+10;

int main()
{
    
      
    string s;
    cin>>s;
    ll ans=0;
    sort(s.begin(),s.end());

    do
    {
    
      
        bool ok=1;
        for(ll i=0;i+1<s.size();i++)
        {
    
      
            if(s[i]==s[i+1])
            {
    
      
                ok=0;
                break;
            }
        }
        if(ok)  ans++;
    }while(next_permutation(s.begin(), s.end()));

    cout<<ans<<endl;
    return 0;
}