사라지는 문자열

문자열 $T$에 대해 다음 두 값을 정의하자.

$D_0(T)$는 $T$의 상대적 홀수 번째 위치에 있는 0의 개수에서 상대적 짝수 번째 위치에 있는 0의 개수를 뺀 값이다.

$D_1(T)$는 $T$의 상대적 홀수 번째 위치에 있는 1의 개수에서 상대적 짝수 번째 위치에 있는 1의 개수를 뺀 값이다.

어떤 문자열이 사라지는 문자열이라면 반드시

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

이다.

인접한 같은 문자 두 개를 지울 때 두 문자는 현재 문자열에서 하나는 홀수 번째 위치, 다른 하나는 짝수 번째 위치에 있다. 따라서 같은 문자의 홀수 번째 개수와 짝수 번째 개수가 각각 하나씩 줄어들고, $D_0,D_1$은 변하지 않는다. 빈 문자열에서는 두 값이 모두 $0$이므로 필요성이 성립한다.

반대로 $D_0(T)=D_1(T)=0$이라면 $T$는 항상 사라진다. 가 비어 있으면 자명하다. 가 비어 있지 않은데 인접한 같은 문자가 없다면 는 또는 꼴의 교대 문자열이다. 이 경우 한 문자는 홀수 번째 위치에만, 다른 문자는 짝수 번째 위치에만 나타나므로 일 수 없다.

따라서 비어 있지 않은 $T$에는 인접한 같은 문자가 존재한다. 그 두 문자를 지워도 $D_0,D_1$은 계속 $0$이고 길이는 $$ 줄어든다. 이를 반복하면 결국 빈 문자열이 된다.

즉, 부분문자열이 사라지는 문자열일 필요충분조건은 $D_0=D_1=0$이다.

이제 원래 문자열의 위치 $i$가 홀수이면 부호를 $+1$, 짝수이면 부호를 $-1$로 둔다. prefix 상태

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

를 다음과 같이 정의한다.

$p_{0,i}$는 $1$번부터 $i$번까지의 0에 대해 위치의 부호를 모두 더한 값이다.

$p_{1,i}$는 $1$번부터 $i$번까지의 1에 대해 위치의 부호를 모두 더한 값이다.

부분문자열 $S_lS_{l+1}\cdots S_r$에서 상대적인 위치의 홀짝은 $$의 홀짝에 따라 원래 위치의 홀짝과 같거나 모두 반대가 된다. 하지만 두 부호가 모두 반대가 되어도 인지 여부는 변하지 않는다.

따라서

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

가 사라지는 문자열일 필요충분조건은

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

이다.

왼쪽부터 prefix 상태를 계산하면서 지금까지 같은 상태가 몇 번 등장했는지 저장한다. 현재 상태가 이전에 $c$번 등장했다면 현재 위치에서 끝나는 사라지는 부분문자열이 $c$개 추가된다. 처음에는 빈 prefix의 상태 $(0,0)$이 한 번 등장했다고 두면 된다.

상태를 map으로 관리하면 $O(N\log N)$, hash map으로 관리하면 평균 $O(N)$에 해결할 수 있다. 메모리 사용량은 $O(N)$이다.

부분문자열의 개수는 최대

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

이고 $N\leq200\,000$이므로 정답은 항상 부호 있는 $64$비트 정수 범위에 들어간다.

Solution written by GPT5.6