문자열 접기

면접 대비

시간 제한1초메모리 제한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$ 이 공백으로 구분되어 주어진다.

각 질문의 답을 질문 순서대로 한 줄에 하나씩 출력한다.