我们先分别讨论两个限制条件,提炼出其中的信息
- t和s字符集相同,代表s中出现的所有字符在t中都有出现
- t的每个位置的字符都和s不同,代表t[i] != s[i]
观察样例我们发现构造方法很多,但是我们需要写出一种简单的,普适的方法,对于aabbc这种情况,我们可以发现,我们可以将s中的所有a全部变成c,所有b全部变成a,所有c全部变成b,这样就满足了两个条件
于是得出做法,可以先得出s中的字符集,然后将s中的字符集中的字符依次替换成上一个字符,第一个字符替换为最后一个字符,等效于修改了字符的映射关系
不难发现可以用set实现字符集,使用map实现修改字符映射关系
但是其实不需要set,我们遍历s,我都将其在map中建立一个自己到自己的映射,那么遍历s后如果map的大小为1,代表只有一个字符不合法输出-1,否则将map中的每个字符键的值替换成上一个字符,第一个字符替换为最后一个字符,然后使用新的映射关系遍历s输出结果即可
#include <bits/stdc++.h> using namespace std; int __t = 1, n; void solve() { string s; cin >> s; map<char, char> mp; for (auto c : s) mp[c] = c; if (mp.size() == 1) { cout << -1 << "\n"; return; } char ov = mp.rbegin()->second; for (auto& [k, v] : mp) swap(v, ov); for (auto i : s) cout << mp[i]; cout << "\n"; return; } int main() { // cin >> __t; while (__t--) solve(); return 0; }