Official Analysis (C++)

Explanation

First, notice that sequences $OW$ and $WO$ can be transformed into a $C$. As an example, we transform $OW$ to $CWW$ and then simplify into $C$. We can also rearrange any two adjacent characters, like $CO$ to $OC$. As an example, we transform $CO$ to $OWWC$ and then simplify to $OC$.

Since we can freely swap characters in a substring, only the frequency of each character is relevant in answering a query.

Let $C$, $W$, and $O$ be the frequency of their respective characters in the queried subarray. We can compute these values with prefix sums.

Notice that if $C + W$ or $C + O$ are even, the answer must be false, because we can't simplify the substring into a single $C$ without $O$ or $W$ characters remaining. This is because the parity of $C + W$ or $C + O$ is always constant, beacuse by performing the expansion or deletion operation, we can never change the parity. (For example, $CWCW$ -> $CW$ or $CW$ -> $COC$, both of which hold the same parity of C + W).

To prove that the substring is valid when $C + W$ is odd and $C + O$ is odd, we can first notice that when these two conditions hold, $W + O$ is even.

Next, we simplify $W$ and $O$ by removing all duplicate pairs. One possibility is that we will be left with $W = 0$ and $O = 0$, meaning that $C$ was odd, and thus it can easily be simplified into one $C$ character.

Otherwise, we will be left with $W = 1$ and $O = 1$, meaning that $C$ was even. By combining the $WC$ pair into a singular $C$, we will be left with an odd amount of $C$, which can be simplified into one $C$ character.

So, to answer a query, we check if $C+W$ and $C+O$ are both odd. Calculating these values can be done using prefix sums.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	string s;
	cin >> s;
	// Calculate prefix array for each character
	vector<array<int, 3>> a(s.size() + 1);

	for (int i = 1; i <= s.size(); i++) {

Copy
s = input()
n = len(s)

# Calculate prefix array for each character
a = [[0, 0, 0] for _ in range(n + 1)]

for i, ch in enumerate(s, 1):
	a[i][0] = a[i - 1][0] + (ch == "C")
	a[i][1] = a[i - 1][1] + (ch == "O")
	a[i][2] = a[i - 1][2] + (ch == "W")

Copy
import java.io.*;
import java.util.StringTokenizer;

public class COWOperations {
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		String s = r.readLine();

		// Calculate the prefix array for each character