Palindromic Indices

题面翻译

题目描述

给定一个回文字符串 $s$ ，它的长度为 $n$ $(2 \leq n \leq 10^5)$ ，问一共有多少种方式使它去掉一个字符后仍是回文字符串。

输入格式

共有 $t$ $(1 \leq t \leq 10^3)$ 组数据，对于每组数据，先输入字符串的长度 $n$ ，再输入回文字符串 $s$ 。

输出格式

对于每组数据，输出一共有多少种方式使输入的字符串去掉一个字符后仍是回文字符串。

数据范围

数据保证所有的 $n$ 之和不超过 $2 \cdot 10^5$ 。

题目描述

You are given a palindromic string $s$ of length $n$ .

You have to count the number of indices $i$ $(1 \le i \le n)$ such that the string after removing $s_i$ from $s$ still remains a palindrome.

For example, consider $s$ = "aba"

1. If we remove $s_1$ from $s$ , the string becomes "ba" which is not a palindrome.
2. If we remove $s_2$ from $s$ , the string becomes "aa" which is a palindrome.
3. If we remove $s_3$ from $s$ , the string becomes "ab" which is not a palindrome.

A palindrome is a string that reads the same backward as forward. For example, "abba", "a", "fef" are palindromes whereas "codeforces", "acd", "xy" are not.

输入格式

The input consists of multiple test cases. The first line of the input contains a single integer $t$ $(1 \leq t \leq 10^3)$ — the number of test cases. Description of the test cases follows.

The first line of each testcase contains a single integer $n$ $(2 \leq n \leq 10^5)$ — the length of string $s$ .

The second line of each test case contains a string $s$ consisting of lowercase English letters. It is guaranteed that $s$ is a palindrome.

It is guaranteed that sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .

输出格式

For each test case, output a single integer — the number of indices $i$ $(1 \le i \le n)$ such that the string after removing $s_i$ from $s$ still remains a palindrome.

样例 #1

样例输入 #1

3
3
aba
8
acaaaaca
2
dd

样例输出 #1

1
4
2

提示

The first test case is described in the statement.

In the second test case, the indices $i$ that result in palindrome after removing $s_i$ are $3, 4, 5, 6$ . Hence the answer is $4$ .

In the third test case, removal of any of the indices results in "d" which is a palindrome. Hence the answer is $2$ .