Palindrome Index

Problem Statement

You are given a string of lower case letters. Your task is to figure out the index of the character on whose removal it will make the string a palindrome. There will always be a valid solution.

In case the string is already a palindrome, then -1 is also a valid answer along with possible indices.

Input Format

The first line contains

Output Format

Print the position (0 index) of the letter by removing which the string turns into a palindrome. For a string, such as

bcbc

we can remove b at index 0 or c at index 3. Both answers are accepted.

Constraints

Sample Input

3
aaab
baa
aaa

Sample Output

3
0
-1

Explanation

In the given input, T = 3,

For input aaab, we can see that removing b from the string makes the string a palindrome, hence the position 3.
For input baa, removing b from the string makes the string palindrome, hence the position 0.
As the string aaa is already a palindrome, you can output 0, 1 or 2 as removal of any of the characters still maintains the palindrome property. Or you can print -1 as this is already a palindrome.

读题时需注意：

题目中先说 “There will always be a valid solution. ”，然后才说“In case the string is already a palindrome, then -1 is also a valid answer along with possible indices.”。注意体会这句话，我们首先应注意到，即使输入的字符串S是个回文串，也可以删除某个字母使其仍为回文串。如果|S|为奇数，则删除中间那个字母，结果串仍为回文串。如果|S|为偶数则删除中间两个相等字符中的任一个，结果串也回文。

完全暴力的解法：

枚举要删除的字母，检查结果串是否回文。复杂度O(N^2)。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAX_N=1e5+10;
 4 char s[MAX_N];
 5 int len;
 6 int opp(int j, int x){
 7     if(x==0){
 8         return len+1-j;
 9     }
10     if(j<x){
11         return len-j<x? len-j: len-j+1;
12     }
13     else{
14         return len+2-j;
15     }
16 }
17 bool ok(int x){
18     int tmp=x?(len-1)>>1:len>>1;
19     for(int i=0, j=1; i<tmp; i++, j++){
20         if(j==x){
21             j++;
22         }
23         if(s[j]!=s[opp(j, x)]){
24             return false;
25         }
26     }
27     return true;
28 }
29 int main(){
30     int T;
31     scanf("%d", &T);
32     while(T--){
33         scanf("%s", s+1);
34         len=strlen(s+1);
35         for(int i=0; i<=len; i++){
36             if(ok(i)){
37                 printf("%d
", i-1);
38                 break;
39             }
40         }
41     }
42     return 0;
43 }

只是这解法过于暴力，TLE。

下面就要引入这道题给我的最大启示了：

寻找有助于简化问题的必要条件

考虑一下上面的单纯暴力算法有那些冗余计算。

首先必须指出一个问题：优化算法的途径是充分考虑问题的特殊性。

其次要注意到：题目要求的是存在性判别，上面的算法枚举被删除字符的位置是无可厚非的。

接着考虑一下使上面的算法达到最坏情况的数据：

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

在这种情况下，上述算法必须枚举到最后一个字符才能确定答案。

我们不难发现一个问题