LMP2 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: kingmessi
Tester: pols_agyi_pols
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given a string. Is it possible to rearrange it so that for any pair (i, j) such that S_i = S_j, the distance (i - j) is odd?

EXPLANATION:

Let’s look at a single character c.
Suppose we rearrange the string, and it appears at positions i_1, i_2, i_3, \ldots, i_k in order from left to right.

Then,

  • If k = 1, there’s only one copy of this character in the string.
    So, it won’t cause any issues anyway.
  • If k = 2, the two copies are at i_1 and i_2.
    We thus want (i_2 - i_1) to be odd.
    This means either i_1 is even and i_2 is odd; or i_1 is odd and i_2 is even.
  • If k = 3, the three copies are at i_1, i_2, i_3.
    We want all three differences to be odd.
    However, this is impossible!
    • Just as before, looking at just i_1 and i_2 tells us that one of them must be odd and the other must be even.
    • But now i_3 must be either even or odd, so it will have the same parity as one of i_1 and i_2.
      This means its distance to the one with same parity will be even, contradicting what we want.

The logic to k = 3 applies to any k \ge 3 as well.

Thus, if any character appears three or more times, the answer is surely "No".

On the other hand, if every character appears \le 2 times, the answer is always "Yes", because for example simply sorting the string will result in a valid rearrangement - characters appearing once have no issues at all, and those appearing twice will be next to each other (so one odd index and one even index).

Thus, we only need to check if every character appears at most twice.
There are many ways to do this, ranging from \mathcal{O}(N) to \mathcal{O}(N^3) (the latter being to iterate over all triplets of indices and check equality).
The constraints are low so any such solution will be accepted.

TIME COMPLEXITY:

\mathcal{O}(N) \sim \mathcal{O}(N^3) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    
    ans = 'Yes'
    for i in range(n):
        eq = 1
        for j in range(i+1, n):
            if s[i] == s[j]: eq += 1
        if eq >= 3: ans = 'No'
    print(ans)