awoo's Favorite Problem (Codeforces 1697C)
Tags: Greedy, two pointers

You are given two strings $$$s$$$ and $$$t$$$, both of length $$$n$$$. Each character in both string is 'a', 'b' or 'c'.In one move, you can perform one of the following actions:   choose an occurrence of "ab" in $$$s$$$ and replace it with "ba";  choose an occurrence of "bc" in $$$s$$$ and replace it with "cb". You are allowed to perform an arbitrary amount of moves (possibly, zero). Can you change string $$$s$$$ to make it equal to string $$$t$$$?

Input: The first line contains a single integer $$$q$$$ ($$$1 \le q \le 10^4$$$) — the number of testcases.The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of strings $$$s$$$ and $$$t$$$.The second line contains string $$$s$$$ of length $$$n$$$. Each character is 'a', 'b' or 'c'.The third line contains string $$$t$$$ of length $$$n$$$. Each character is 'a', 'b' or 'c'.The sum of $$$n$$$ over all testcases doesn't exceed $$$10^5$$$.

Output: For each testcase, print "YES" if you can change string $$$s$$$ to make it equal to string $$$t$$$ by performing an arbitrary amount of moves (possibly, zero). Otherwise, print "NO".


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

Sample Outputs:
YES
NO
YES
YES
NO

Solution (Python):
from collections import *
from functools import *
import sys
input = lambda : sys.stdin.readline().rstrip()
Z = int(input())
for _ in range(Z):
    n = int(input())
    ss = input()
    tt = input()
    stack = deque()
    f = 0
    for (i, t) in enumerate(tt):
        s = ss[i]
        if stack:
            if s == t:
                if stack[-1][0] == s or stack[-1][1] == s:
                    pass
                else:
                    f = 1
                    break
            elif (s, t) == stack[-1]:
                stack.append((s, t))
            elif (t, s) == stack[-1]:
                stack.pop()
            else:
                f = 1
                break
        elif not stack:
            if s == t:
                pass
            elif ord(t) - ord(s) == 1:
                stack.append((s, t))
            else:
                f = 1
                break
    if f or stack:
        print('NO')
    else:
        print('YES')

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    s = list(input().strip())
    t = input().strip()
    idx1 = start = 0
    while idx1 < n:
        (c1, c2) = (s[idx1], t[idx1])
        if c1 == c2:
            idx1 += 1
            continue
        if c1 == 'c':
            return 'NO'
        elif c1 == 'a':
            if c2 == 'c':
                return 'NO'
            j = max(start, idx1 + 1)
            while j < n and s[j] != 'b':
                if s[j] == 'c':
                    return 'NO'
                j += 1
            if j == n:
                return 'NO'
            (s[idx1], s[j]) = (s[j], s[idx1])
            start = j + 1
        else:
            if c2 == 'a':
                return 'NO'
            j = max(start, idx1 + 1)
            while j < n and s[j] != 'c':
                if s[j] == 'a':
                    return 'NO'
                j += 1
            if j == n:
                return 'NO'
            (s[idx1], s[j]) = (s[j], s[idx1])
            start = j + 1
        idx1 += 1
    if s[-1] != t[-1]:
        return 'NO'
    return 'YES'
for _ in range(int(input())):
    print(solve())

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    s = input()
    t = input()
    if s.count('b') != t.count('b'):
        print('NO')
        continue
    j = 0
    for i in range(n):
        if s[i] == 'b':
            continue
        while t[j] == 'b':
            j += 1
        if s[i] != t[j] or (s[i] == 'a' and i > j) or (s[i] == 'c' and i < j):
            print('NO')
            break
        j += 1
    else:
        print('YES')