Problem A. Super-palindrome

You are given a string that is consistedof lowercase English alphabet. You are supposed to change it into asuper-palindrome string in minimum steps. You can change one character instring to another letter per step.

A string is called asuper-palindrome string if all its substrings with an odd length are palindromestrings. That is, for a string s, if its substring s_i···j satisfies j −i + 1 is oddthen s_i_+k= s_j−k fork= 0,1,··· ,j− i + 1.

Input

The first line contains an integer T (1 ≤ T ≤100) representing the number of test cases.

For each test case, the only line containsa string, which consists of only lowercase letters. It is guaranteed that thelength of string satisfies 1 ≤ |s| ≤ 100.

Output

For each test case, print one line with aninteger refers to the minimum steps to take.

Example

standard input

standard output

ncncn

aaaaba

aaaabb

Explanation

For second testcase aaaaba, just change letter bto a in one step.

题目描述：给你一个字符串，问你需要更改里面多少个字符，使得原字符串变为一个超级回文串。超级回文串是指字串为奇数长度的都为回文串的串。

题目分析：分析样例之后容易得出，对于这样一个超级回文串，只有两种情况可以满足。

一为串内所有的字符都是相同的。

二是该串只有两种字符组成，且这两种字符是交替出现的。

能够发现这个规律的话，这道题就可以进行模拟。因为数据范围很小（100而已），因此我们可以直接进行暴力的匹配。

我们首先先将串中不相同的字符储存起来，枚举两种字符的种类，再跟原串进行匹配，最后去最小的更改量即可。

总结：最近做字符串算法做得有些多了，上来拿到题直接就往Manache上面去想了（还好队友很给力），对于这些题还得拓宽思维才行！！

#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
string str,tmp;
bool vis[maxn];
int main()
{
    int t;
    cin>>t;
    while(t--){
        cin>>str;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<str.length();i++){
            if(!vis[str[i]-'a']){
                tmp+=str[i];
                vis[str[i]-'a'];
            }
        }
        int ans=0x3f3f3f3f;
        for(int i=0;i<tmp.length();i++){
            for(int j=0;j<tmp.length();j++){
                char c[2];
                c[0]=tmp[i],c[1]=tmp[j];
                int cnt=0;
                for(int k=0;k<str.length();k++){
                    if(str[k]!=c[k%2]) cnt++;
                }
                ans=min(ans,cnt);
            }
        }
        cout<<ans<<endl;
        tmp.clear();//记得清零，否则会影响下一组数据
    }
}