문자열 접기 (Hard)

시간 제한1.5초메모리 제한1024 MB

요약

문자열 S의 구간 [l, r]을 두 인접 문자 사이에서 한 번 접을 때, 겹치는 같은 글자 쌍의 최대 개수를 구합니다.

문제

기다란 종이에 알파벳 대문자로만 이루어진 문자열이 한 줄로 쓰여 있다. 예를 들어 아래 그림과 같이 종이에 “ABAACA”가 쓰여 있다고 가정하자.

이제 이 종이를 한 번만 접는다. 종이는 서로 이웃한 문자 사이에서만 접을 수 있다. 예를 들어 아래 그림과 같이 종이를 $4$ 번째 문자와 $5$ 번째 문자 사이에서 접을 수 있다.

접었을 때 서로 맞닿은 문자 쌍 중에서 같은 문자가 맞닿은 쌍의 개수가 이 접기의 점수가 된다. 예를 들어 위의 접기의 점수는 $1$ 점이다. 하지만 아래 그림과 같이 $3$ 번째 문자와 $4$ 번째 문자 사이에서 종이를 접으면 점수는 $2$ 점이 된다.

알파벳 대문자로만 이루어진 문자열 $S$ 가 주어지면, 다음 형식의 질문 $Q$ 개에 답해야 한다.

$l \ r$ : 문자열 $S$ 의 $l$ 번째 문자, $(l+1)$ 번째 문자, $\cdots$ , $r$ 번째 문자가 차례대로 종이에 쓰여 있을 때, 종이를 한 번 접어서 얻을 수 있는 최대의 점수는 몇 점인가?

첫 번째 줄에 문자열의 길이를 나타내는 정수 $N$ 이 주어진다.

두 번째 줄에 알파벳 대문자로만 이루어진 문자열 $S$ 가 주어진다.

세 번째 줄에 정수 $Q$ 가 주어진다.

네 번째 줄부터 $Q$ 개 줄에 걸쳐 위에서 설명한 질문을 나타내는 정수 $l$ , $r$ 이 공백으로 구분되어 주어진다.

각 질문의 답을 나타내는 정수를 순서대로 한 줄에 하나씩 출력한다.