Vanishing String

For a string $T$, define the following two values.

$D_0(T)$ is the number of 0s at relative odd positions of $T$ minus the number of 0s at relative even positions.

$D_1(T)$ is the number of 1s at relative odd positions of $T$ minus the number of 1s at relative even positions.

If a string is vanishing, then necessarily

$$D_0(T)=D_1(T)=0.$$

When two equal adjacent characters are deleted, one of them is at an odd position of the current string and the other is at an even position. Therefore, the odd-position count and the even-position count of that character both decrease by one, so $D_0$ and $D_1$ do not change. Both values are $0$ for the empty string, proving necessity.

Conversely, if $D_0(T)=D_1(T)=0$, then $T$ always vanishes. If is empty, this is trivial. If is nonempty and has no equal adjacent characters, then it must alternate as or . In such a string, one character appears only at odd positions and the other only at even positions, so both and cannot be .

Thus, every nonempty such $T$ has two equal adjacent characters. Deleting them preserves $D_0=D_1=0$ and reduces the length by $$. Repeating this process eventually produces the empty string.

Hence, a substring is vanishing if and only if $D_0=D_1=0$.

Now give position $i$ sign $+1$ if $i$ is odd and sign $-1$ if $i$ is even. Define the prefix state

$$P_i=(p_{0,i},p_{1,i}),$$

where $p_{0,i}$ is the sum of these signs over all 0s in positions $1$ through $i$, and $p_{1,i}$ is defined similarly for s.

For a substring $S_lS_{l+1}\cdots S_r$, its relative position parity is either the same as the original parity or completely reversed, depending on the parity of . Reversing every sign does not change whether both values are zero.

Therefore,

$$S_lS_{l+1}\cdots S_r$$

is vanishing if and only if

$$P_r=P_{l-1}.$$

Scan the string from left to right while counting how many times each prefix state has appeared. If the current state has already appeared $c$ times, then exactly $c$ new vanishing substrings end at the current position. Initially, the empty prefix state $(0,0)$ has appeared once.

Using a map gives $O(N\log N)$ time, while a hash map gives expected $O(N)$ time. The memory complexity is $O(N)$.

The number of substrings is at most

$$\frac{N(N+1)}{2}.$$

Since $N\leq200\,000$, the answer always fits in a signed 64-bit integer.

Solution written by GPT5.6