팰린드롬 만들기

면접 대비

시간 제한2초메모리 제한2048 MB

요약

소문자로 이루어진 문자열에서 거리가 2인 두 문자를 맞바꾸어 팰린드롬을 만들 수 있는지 판별합니다.

난이도: 보통10점 중 5점
유형: 해시맵, 문자열, 수학
정답자: 아직 제출이 없습니다

문제

소문자 영어 알파벳으로 이루어진 문자열 $s$ 가 있다. 0번 이상의 연산을 거쳐 이 문자열을 팰린드롬으로 바꾸려고 한다. 한 번의 연산에서 문자열 안의 두 문자를 서로 교환할 수 있다. 단, 두 문자의 위치 차이가 정확히 $2$ 인 경우에만 교환할 수 있다. 즉 두 문자 사이에 문자가 정확히 하나 있어야 한다. $s$ 를 팰린드롬으로 바꿀 수 있는지 판별하라. 팰린드롬은 앞에서 읽으나 뒤에서 읽으나 같은 문자열이다.

입력

첫 줄에 테스트 케이스의 개수 $t$ ( $1 \le t \le 10^5$ )가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 정수 $n$ ( $1 \le n \le 10^5$ )이 주어진다. 둘째 줄에는 길이가 $n$ 인 문자열 $s$ 가 주어진다. $s$ 는 소문자 영어 알파벳으로 이루어진다. 모든 테스트 케이스의 $n$ 을 합한 값은 $10^5$ 을 넘지 않는다.

출력

각 테스트 케이스마다 주어진 문자열을 위 규칙으로 팰린드롬으로 바꿀 수 있으면 YES, 그렇지 않으면 NO를 한 줄에 출력한다.

예제1

예제 1

입력

8
6
acbbca
6
acbbac
6
aaaaaa
7
abcacba
9
abcbcecea
1
b
2
ca
2
cc

예상 출력

YES
NO
YES
YES
YES
YES
NO
YES