EQUATEST - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given strings S and T, containing only a’s and b’s.
In one move, you can choose an a in either string and replace it with ab.

Is it possible to make both strings equal eventually?

EXPLANATION:

Our operation is equivalent to “choose an a, and insert a b after it”.
Note that this operation doesn’t allow us to change the number of occurrences of a at all.

So, if S and T don’t have the same number of a’s, it’s definitely impossible to make both strings equal.
We’re now left with the case when they do have an equal number of a’s.

Since our operation is “insert a b after an a”, we definitely cannot do anything about indices that are to the left of any a.
That is, if p is the leftmost index in S containing a, and q is the leftmost index in T containing a, we can’t do anything at all about indices \leq p in S or \leq q in T.

In particular, the leftmost occurrence of a in S will always be at index p, and the leftmost occurrence of a in T will always be an index q, no matter how many operations are performed.
So, if we want S = T in the end, we must also have p = q.

On the other hand, if we do indeed have p = q, it’s always possible to make S = T.

How?

Till index p, both strings are already equal.

Now, we have S_p = T_p = \text{a}.
There are two possibilities:

  1. There are no more a’s in the strings.
    Then, repeatedly insert b’s after index p in S and/or T till there’s an equal number of b’s in them both, at which point the strings are equal.
  2. There exists another a. Let this be at index p_1 in S and q_1 in T.
    Then, repeatedly insert b’s after index p in S$ and/or T till p_1 and q_1 become equal (this is always possible, because inserting in S will increase p_1 by 1, and inserting in T will increase q_1 by 1).
    Once p_1 = q_1, jump to that index and repeat the process.

In summary, we only have to make a couple of checks:

  1. Check if S and T have the same number of a’s.
  2. Check if the leftmost occurrence of a in both S and T is at the same index.
    • If there are no a’s in S and T, this instead turns into a simple length check, i.e, N = M must hold.

If both conditions are satisfied, the answer is Yes, otherwise it’s No.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, m = map(int, input().split())
    s = input()
    t = input()
    
    if s.count('a') == t.count('a'):
        p = s.find('a')
        q = t.find('a')
        if p == -1: p = n
        if q == -1: q = m
        
        print('Yes' if p == q else 'No')
    else: print('No')
1 Like