완성된 문자열을 X라고 하자.
길이가 i인 접두사 X[1..i]가 팰린드롬이면, 그 접두사의 첫 문자와 마지막 문자가 같아야 한다. 따라서 모든 i (1≤i≤N)에 대하여 X1=Xi이다. 즉, X의 모든 문자는 같아야 한다.
이제 S에 이미 적혀 있는 알파벳 대문자만 확인하면 된다.
- 알파벳 대문자가 하나도 없다면, 공통 문자로 알파벳 대문자 26개 중 아무거나 고를 수 있으므로 답은 26이다.
- 적혀 있는 모든 알파벳 대문자가 같다면, 공통 문자는 그 문자로 유일하므로 답은 1이다.
- 서로 다른 두 알파벳 대문자가 존재한다면, 모든 문자를 같게 만들 수 없으므로 답은 0이다.
각 테스트 케이스를 한 번 순회하면 되므로 시간 복잡도는 O(N)이고, 추가 공간 복잡도는 O(1)이다.
