Awoo's favorite problem (priority queue)

Original link

Title Description

Here are two strings s and t, All the lengths are n. Each character in both strings is ’a’, ‘b’ or ’c’.

In one operation , You can do one of the following :

choice s What happened in “ab”, Replace it with “ba”;

choice s What happened in “bc”, And replace it with “cb”.

You can perform any number of moves ( It could be zero ). You can change the string s Make it equal to string t Do you ?

sample input

5
3
cab
cab
1
a
b
6
abbabc
bbaacb
10
bcaabababc
cbbababaac
2
ba
ab

sample output

YES
NO
YES
YES
NO

---

Algorithm

( greedy + Priority queue + simulation )

Greedy strategy ： Record the subscript of each letter through the priority queue , Each time if there are interchangeable letter pairs, take the nearest subscript and observe whether they can be exchanged , If not, the letter will pop up directly .

C++ Code

Time complexity $O(nlogn)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
ll a[N],s[N];

void solve()
{
    int n;
    cin >> n;
    string s,t;
    cin >> s >> t; 
    vector<int> v1(3,0),v2(3,0);
    for (int i = 0;i < n;i ++ ) v1[s[i] - 'a'] ++;
    for (int i = 0;i < n;i ++ ) v2[t[i] - 'a'] ++;

    if (v1 == v2) {
        priority_queue<int,vector<int>,greater<int>>a,b,c;
        for(int i = 0;i < n;i ++ ) {
            if(s[i] == 'a') a.push(i);
            if(s[i] == 'b') b.push(i);
            if(s[i] == 'c') c.push(i);
        }
        for (int i = 0;i < n;i ++ ) {
            if (s[i] == t[i]) {
                if (s[i] == 'a') a.pop();
                else if (s[i] == 'b') b.pop();
                else c.pop();
            }else {
                if (s[i] == 'a' && t[i] == 'b') {
                    if (!b.empty() && (c.empty() || b.top() < c.top())) {
                        int index = b.top();
                        b.pop();
                        swap(s[i],s[index]);
                        a.pop();
                        a.push(index);
                        continue;
                    }
                }else if (s[i] == 'b' && t[i] == 'c') {
                    if (!c.empty() && (a.empty() || c.top() < a.top())) {
                        int index = c.top();
                        c.pop();
                        swap(s[i],s[index]);
                        b.pop();
                        b.push(index);
                        continue;
                    }
                }
                puts("NO");
                return;
            }
        } 
        puts("YES");
    }else puts("NO");
}
int main()
{
    int t;
    cin >> t;
    while (t -- ) solve();
    return 0;
}