목걸이

보석 세공사 Frank는 배치가 미리 정해진 특별한 목걸이를 만들어야 한다. 각 구슬은 금(G), 은(S), 청동(B) 중 하나이며, 같은 색 구슬은 서로 구별할 수 없고 자유롭게 교체할 수 있다. 완성된 목걸이는 닫힌 고리이다. 조립이 끝나면 Frank는 실의 양 끝을 잇는데, 이음매는 인접한 어느 두 구슬 사이에나 올 수 있으므로 배치는 원형(순환)으로 본다.

Frank는 이미 모든 구슬을 하나의 곧은 핀에 꿰어 두었지만 순서가 목걸이와 다를 수 있다. 그는 항상 핀의 왼쪽 끝에서 다음 구슬을 하나 빼내어 다음 중 하나를 한다.

• 지금까지 만든 실의 양쪽 끝 중 한 곳에 곧바로 꿴다, 또는
• 나중에 쓰기 위해 따로 빼서 더미에 놓아 둔다.

또한 언제든지 더미에서 필요한 색의 구슬을 꺼내 실의 양쪽 끝 중 한 곳에 꿸 수 있다. 작업실이 어수선하고 구슬이 귀하기 때문에, Frank는 어느 한 순간에 따로 놓인 더미에 있는 구슬 수의 최댓값을 최소로 만들고자 한다. 핀에서 실로 곧바로 꿴 구슬은 더미에 들어가지 않는다.

목표 배치와 핀에 꿰인 구슬의 순서가 주어질 때, 이 최솟값을 구하여라.

첫째 줄에 구슬의 개수를 나타내는 정수 $L$ ($1 \le L \le 1000$)이 주어진다. 둘째 줄에는 목걸이 배치를 나타내는 길이 $L$의 문자열이 주어지며, 각 문자는 G, S, B 중 하나이다(어느 지점에서 잘라 편 것으로, 원형으로 읽는다). 셋째 줄에는 핀에 꿰인 구슬을 Frank가 왼쪽 끝에서 빼내는 순서대로 나타낸 길이 $L$의 문자열이 주어진다. 핀의 구슬로 목걸이를 반드시 만들 수 있음이 보장된다(두 문자열의 색 구성은 동일하다).

조립 과정 중 어느 순간에든 따로 놓인 더미 크기의 최댓값이 가질 수 있는 최솟값을 정수 하나로 출력한다.

• 첫 번째 예제에서 배치는 금과 은이 번갈아 나오므로 어떤 구슬이든 양옆 이웃은 반대 색이다. Frank가 어떤 은 구슬로 시작하더라도 그 양옆 이웃은 모두 금이어야 하는데, 핀은 은 구슬 네 개를 먼저 내보낸다. 금 구슬이 나오기 전까지 은 세 개가 더미에서 기다려야 하므로 더미 크기는 3에 이른다.
• 두 번째 예제에서 Frank는 모든 구슬을 핀에서 곧바로 꿸 수 있다. 실의 한쪽 끝에서는 금 구슬을, 반대쪽 끝에서는 은 구슬을 늘려 가면 아무것도 따로 놓을 필요가 없어 답은 0이다.