Arts and Computing Students (Problem A, CS3233 Midterm Contest 2025, 2025)
Time limit: 1 sec
Memory limit: 1024 MB

# Problem Statement

To encourage interdisciplinary collaboration, the School of Computing has decided to hold a dinner event for students in School of Computing and the Faculty of Arts and Social Sciences. The event will be held in a large hall with a long table that can seat $2N$ students. Interestingly, the $2N$ seats are arranged on a single line, with $N$ pairs of seats. Seats belonging to the same pair are adjacent in the line. Each seat will either contain a student from the School of Computing, a student from the Faculty of Arts and Social Sciences, or be empty. Two students sitting next to each other within the same pair of seats are called "buddies". There are at most $N$ pairs of buddies by definition.

The Dean of the School of Computing suspects that School of Computing students will start Leetcoding on their laptops if they do not have a student from the Faculty of Arts and Social Sciences as a buddy. To prevent this, the Dean wants to rearrange the students such that each student from the School of Computing has a buddy from the Faculty of Arts and Social Sciences.

The Dean can perform the following operation: he can choose a student sitting next to an empty seat and move that student to the empty seat. These two seats need not belong to the same pair.

Given the initial arrangement of students, can you help the Dean determine if it is possible to rearrange the students such that each student from the School of Computing has a buddy from the Faculty of Arts and Social Sciences?

# Input

The first line of input contains an integer $N$ $(1 \leq N \leq 2 \times 10^5)$, the number of pairs of seats.

The second line of input contains a string of length $2N$ consisting of the characters `C`, `A`, and `.`. The $i$-th character is `C` if the student in the $i$-th seat is from the School of Computing, `A` if the student is from the Faculty of Arts and Social Sciences, and `.` if the seat is empty.

# Output

If it is not possible to rearrange the students such that each student from the School of Computing has a buddy from the Faculty of Arts and Social Sciences, output `NO`.

Otherwise, ouptut `YES` on the first line. Output a string of length $2N$ on the second line, where the $i$-th character is `C` if the student in the $i$-th seat is from the School of Computing, `A` if the student is from the Faculty of Arts and Social Sciences, and `.` if the seat is empty. This string should represent the final arrangement of students after the Dean has rearranged the students.

If there are multiple possible answers, you may output any of them.

# Sample Input #1
```
3
C.AAAC
```
# Sample Output #1
```
YES
CAA.AC
```
# Sample Input #2
```
4
AAA.CCAC
```
# Sample Output #2
```
NO
```
# Sample Input #3
```
4
CA.A.C.A
```
# Sample Output #3
```
YES
CA..ACA.
```

Sample inputs:
3
C.AAAC

4
AAA.CCAC

4
CA.A.C.A

Sample outputs:
YES
CAA.AC

NO

YES
CA..ACA.

# Solution Analysis

There are two solutions to this problem:

- **Dynamic Programming**: Observe that our ultimate goal is to pair up the students as much as possible, as we risk running out of space (there are only $N$ pairs of seats) if we do not pair them up sufficiently. We can let $\texttt{dp}[i]$ be the minimum number of pairs needed to pair up students $1, 2, \ldots, i$ such that the constraint is satisfied. To compute $\texttt{dp}[i]$, it suffices to condition on whether student $i$ is paired with student $i - 1$:

  $$
  \texttt{dp}[i] = \min \left\{
  \begin{array}{ll}
  \texttt{dp}[i - 2] + 1 & \text{if student } i \text{ and } i-1 \text{ forms a valid pair} \\
  \texttt{dp}[i - 1] + 1 & \text{if student } i \text{ can sit alone (i.e. arts student)}
  \end{array}
  \right.
  $$

  A solution exists if $\texttt{dp}[\#\text{ students}] \leq N$, and we can backtrack to find the construction.

- **Greedy**: Notice that if we have a computing student at the beginning / end of the array or we have two consecutive computing students, then their seating arrangements are fixed. (For example, if we have ACCA as a substring, we know that the pairs must be AC and CA.) We first split the string whenever we see **ACCA**. For the remaining chunks without two consecutive computing students, we can greedily seat them using $\left\lfloor \frac{\# \text{students}}{2} \right\rfloor$ pairs (if we have more computing students than arts students, then this is clearly impossible). It is easy to see that this greedy strategy minimizes the number of pairs needed to seat all students.

P.S. Many teams attempted to code a (wrong) greedy solution right away. It’s a better idea to (informally) justify the correctness of your greedy approach or try coming up with counter-examples before coding. When in doubt, dynamic programming is the safe choice to go with, as long as it’s fast enough!



Special judge (C++ scorer):