F-三生三世

题目链接.

题目描述：

秦皇岛的海风轻轻地唱着歌唤醒了水上的涟漪，冬日的阳光把沙滩洒满了金黄。
BD哥在沙滩上留下了一串串脚印，突然他发现了一个石碑，上面刻着“HQDB”，下面还写着一个古老的年份。BD哥不由得想起了自己的ID：QBDH
“这个ID也太像我了吧？难道我曾经来过这个世界，那个年份就是上一世的我降临或者离去的时间？”BD哥不由得思考了起来。
“就算没有白浅夜华三生三世的爱情，有一个三生三世的灵魂也能羡煞众人啊！”单身二十多年的BD哥想。
BD哥认为，如果某一个ID是他的ID的全排列的一种，且和他的ID不一样，
便认为这个ID是他的前世，现在告诉你这个ID和BD哥的ID，请你帮忙判断，这个ID是不是他的前世。

输入描述：

输入的第一行包含一个整数n，代表字符串ID的长度。(n<=2e5)
接下来两行分别给出一个长度为n的字符串，可能包含所有大写字母及小写字母，先给出BD哥的ID，下一行给出需要判断的ID。

输出描述：

输出yes代表这个ID是BD哥的前世，no代表不是。

示例1

输入
4
QBDH
BQDH

输出
yes

示例2

输入
5
jwjnb
jwjnb

输出
no

思路详解

阅读题目加粗黑体字可知，我们只需要判断第二个字符串是否为第一个全排列中的一种即可，刚开始的想法也许是去全排列第一个字符串的所有情况，再判断第二个字符串是否与其中一种情况相同，但注意输入描述中的id长度最大可达2e5，无论是用dfs深搜全排列还是用STL已有的功能函数next_permutation（），很明显已经预见超时的结局了，所以此时我们应该抓住后者字符串满足前者字符串全排列情况的条件来做：

①第二个字符串长度不能大于前者（由全排列可知：可以小于第一个字符串的长度）且二个字符串不能相同（见样例二）。
②第二个字符串拥有的每种字符元素必须在第一个字符串中能找到，即第二个字符串不存在新元素。
③基于上面两点以及全排列的知识，第二个字符串每种元素的映射值 ≤ 第一个字符串对应元素的映射值，例如：
s1:aab s2:ab
t1[a] = 2, t1[b] = 1; t2[a] = 1,t2[b] = 1;
t2对应的下标a，b的映射值都大于t1对应元素的映射值，故 s2为s1全排列。

根据以上三点条件，就可以利用STL中set集合的去重性和map映射来将s1、s2中的元素和值分别置入至两种容器中，便于后续的处理。

#include<bits/stdc++.h>
using namespace std;
map<char, int>a, b;
set<char> t1, t2;
int main() {
  int n;
  cin >> n;
  //建议使用string作为字符串类型，方便后续第②条件的查找
  string s1, s2;
  cin >> s1 >> s2;
  //判断最后结果是否为全排列中的一种情况，1为不是，0为是
  int flag = 0;
  //①条件一判断
  if (s1 == s2 || s2.length() > n) {
    flag = 1;
  } else {
  //将元素和元素值置入两种容器中
    for (int i = 0; i < n; i++) {
      a[s1[i]]++;
      t1.insert(s1[i]);   
    }
    for (int i = 0; i < s2.length(); i++) {
      b[s2[i]]++;
      t2.insert(s2[i]);
    }
    set<char>::iterator it;
    for (it = t2.begin(); it != t2.end(); it++) {
      //②查找是否存在新元素
      if (s1.find(*it) == string::npos) {
        flag = 1;
        break;
      }
      //③判断同一个字母在两个字符串的映射值关系
      if (b[*it] > a[*it]) {
        flag = 1;
        break;
      }
    }
  }
  if (flag == 1) {
    cout << "no" << endl;
  } else {
    cout << "yes" << endl;
  }
}