플린드롬 만들기

완성된 문자열을 $X$라고 하자.

길이가 $i$인 접두사 $X[1..i]$가 팰린드롬이면, 그 접두사의 첫 문자와 마지막 문자가 같아야 한다. 따라서 모든 $i$ ($1 \leq i \leq N$)에 대하여 $X_1=X_i$이다. 즉, $X$의 모든 문자는 같아야 한다.

이제 $S$에 이미 적혀 있는 알파벳 대문자만 확인하면 된다.

• 알파벳 대문자가 하나도 없다면, 공통 문자로 알파벳 대문자 26개 중 아무거나 고를 수 있으므로 답은 $26$이다.
• 적혀 있는 모든 알파벳 대문자가 같다면, 공통 문자는 그 문자로 유일하므로 답은 $1$이다.
• 서로 다른 두 알파벳 대문자가 존재한다면, 모든 문자를 같게 만들 수 없으므로 답은 $0$이다.

각 테스트 케이스를 한 번 순회하면 되므로 시간 복잡도는 $O(N)$이고, 추가 공간 복잡도는 $O(1)$이다.