가장 긴 막대 자석

면접 대비

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

요약

N과 S로 이루어진 문자열에서 앞 절반이 모두 한 문자이고 뒤 절반이 모두 다른 문자이며 두 문자의 개수가 같은 가장 긴 연속 부분 문자열을 찾는다.

난이도: 보통10점 중 6점
유형: 문자열, 투 포인터, 그리디, 누적 합
정답자: 아직 제출이 없습니다

문제

막대 자석 문자열은 문자 N과 S로만 구성되면서 다음과 같은 조건을 만족하는 문자열이다: 막대 자석 문자열에 등장하는 N의 개수와 S의 개수는 동일하며, 문자열의 앞쪽 절반을 구성하는 문자는 모두 N이거나 모두 S이다. 예를 들어, NS, NNSS, SSSNNN 등은 막대 자석 문자열이지만, SNS, NNNSS, NSNS 등은 막대 자석 문자열이 아니다.

윤이는 문자 N과 S로 구성된 문자열을 가지고 있다. 윤이는 이 문자열의 부분 문자열 중에서 가장 긴 막대 자석 문자열을 찾고자 한다. 부분 문자열이란 문자열의 연속된 일부를 의미한다. 윤이가 주어진 문자열의 부분 문자열 중에서 찾을 수 있는 가장 긴 막대 자석 문자열의 길이는 얼마인지 구하시오.

입력

첫 번째 줄에 문자열의 길이 $K$ 가 주어진다. ( $1\leq K\leq 300\ 000$ )

두 번째 줄에 문자 N과 S로만 구성된 길이 $K$ 의 문자열이 주어진다.

출력

주어진 문자열의 부분 문자열 중에서 가장 긴 막대 자석 문자열의 길이를 출력한다. 만약 막대 자석 문자열을 찾을 수 없다면, 대신 $0$ 을 출력한다.

예제2

예제 1
입력
```
8
NSSSNNSN
```
예상 출력
```
4
```
예제 2
입력
```
5
NNNNN
```
예상 출력
```
0
```