Igor Perić

A. Palindromic Indices

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

You are given a palindromic string s of length n.

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

For example, consider s = “aba”

1. If we remove s1 from s, the string becomes “ba” which is not a palindrome.
2. If we remove s2 from s, the string becomes “aa” which is a palindrome.
3. If we remove s3 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.

Input

The input consists of multiple test cases. The first line of the input contains a single integer t (1≤t≤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≤n≤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⋅10^5.

Output

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

Example input

3
3
aba
8
acaaaaca
2
dd

Example output

1
4
2

Note

The first test case is described in the statement.

In the second test case, the indices i that result in palindrome after removing si 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.

Solution

Brute-force solution is to remove each character and check if the remaining string is palindrome, which has a complexity of O(N^2).

We can do better. First, we have to realize that removing any character at index i will shift all of the remaining letters after index i to the left, breaking the palindrome in most of the cases. The only time the palindrome won’t be broken is if the removed character belongs to the consecutive series of the same letters in the middle of the palindrome.

To show this is true we will represent our palindrome X as a concatenation of three strings: prefix P, center C and suffix S, where P = reverse(S) and center is a string made of all the same letters, so X = P + C + S. Since we can remove only a single letter, removing anything from either P or S will break the constraint P = reverse(S), so the resulting string won’t be a palindrome. The only remaining option is to remove a character from C.

Now, to prove that removing any letter from C works, we will have to consider the parity of lengths of X, P, C and S. Irrelevant of the parity of the length of X, strings P and S have the same length, so their sum must be even. This means that the parity of C is equal to the parity of X, which makes C “the center” of the palindrome. If after deleting anything from C we get a palindrome, the X will stay palindrome as well. This is always true since C is made of a series of repeated letters.

So the only thing we need to do is to count the number of repeated letters in the middle of the string, which has a complexity of O(N) – way better than O(N^2) brute force.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(){

    int t;
    cin >> t;
    while (t--) {
        int n; cin >> n;
        string s; cin >> s;

        int sol = 0;
        int x = n / 2;
        char c = s[x];
      
        // move left
        for (int i=x;i>=0;i--) {
            if (s[i] != c) break;
            sol++; 
        }
		
      	// move right
        for (int i=x+1;i<n;i++) {
            if (s[i] != c) break;
            sol++; 
        }

        cout << sol << endl;
    }

    return 0;
}