codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1697C.md (1420B)


      1 Source: https://codeforces.com/problemset/problem/1697/C
      2 
      3 C. awoo's Favorite Problem
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given two strings $s$ and $t$, both of length $n$. Each character in both string is 'a', 'b' or 'c'.
     22 
     23 In one move, you can perform one of the following actions:
     24 
     25 * choose an occurrence of "ab" in $s$ and replace it with "ba";
     26 * choose an occurrence of "bc" in $s$ and replace it with "cb".
     27 
     28 You are allowed to perform an arbitrary amount of moves (possibly, zero). Can you change string $s$ to make it equal to string $t$?
     29 
     30 Input
     31 
     32 The first line contains a single integer $q$ ($1 \le q \le 10^4$) — the number of testcases.
     33 
     34 The first line of each testcase contains a single integer $n$ ($1 \le n \le 10^5$) — the length of strings $s$ and $t$.
     35 
     36 The second line contains string $s$ of length $n$. Each character is 'a', 'b' or 'c'.
     37 
     38 The third line contains string $t$ of length $n$. Each character is 'a', 'b' or 'c'.
     39 
     40 The sum of $n$ over all testcases doesn't exceed $10^5$.
     41 
     42 Output
     43 
     44 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".
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 5
     52 
     53 3
     54 
     55 cab
     56 
     57 cab
     58 
     59 1
     60 
     61 a
     62 
     63 b
     64 
     65 6
     66 
     67 abbabc
     68 
     69 bbaacb
     70 
     71 10
     72 
     73 bcaabababc
     74 
     75 cbbababaac
     76 
     77 2
     78 
     79 ba
     80 
     81 ab
     82 ```
     83 
     84 Output
     85 
     86 ```
     87 YES
     88 NO
     89 YES
     90 YES
     91 NO
     92 ```