原题
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
大黄有故事 2016-12-15 1353浏览量
简介： 给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？ 输出需要删除的字符个数。 输入描述: 输入数据有多组，每组包含一个字符串s，且保证:1
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。
输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:
对于每组数据，输出一个整数，代表最少需要删除的字符个数。
输入例子:
abcda
输出例子:
2
2
回文串中。最后一次出现的位置。必定对应镜像的位置。
后续遍历字符串。标记每个字符第一次出现的位置，遍历到两次的字符，就标记其第二次出现的位置。如果这个字符没有前后对应位置，就标记其自己的位置。
样例abababa
对于str[6] a来说，倒叙遍历中，a第一次出现。对应从正序第一次出现再下标0
对于str[4] a来说，倒叙遍历中，a第二次出现。对应从正序第二次出现再下标2
对于str[3] b来说，倒叙遍历中，b第三次出现。对应从正序第三次出现再下标3
对于str[2] a来说，倒叙遍历中，a第三次出现。对应从正序中已经没有再出现的位置。标记为2本身
这番操作得到一个数组，对于这个数组。如果回文串是正常的回文串。其下标值，应该是以中心为对称的严格递增递减。
但是对于本题中，中间可能出现无关字符的，举例如下
样例a1b2a1b2a3b4a
对于这个数组来讲。按照回文串先递增再递减的规律
可以根据数组直接找出源数据中的回文串。
例如，
a1b1a,数组中下标01210
abaaba,数组中下标024420
目标串abababa,数组中下标0246420
数组获取过程优化。
如果倒叙遍历字符，首次出现就从下标0到其本身下标中查询。
第二次出现，就从第一次出现的位置到其本身中查询，
。。。
只需要记录其上一次出现的位置。就能优化查询区间，
如果其上一次出现位置在查询位置的后面。就标记为当前位置
int findchar(const string str, int begin, int end,const char target)//查找target第一次出现位置，
//查找范围为str[begin,end]
{
for (int i = begin; i <= end; i++)
{
if (str[i] == target)
{
return i;
}
}
return end;//如果没找到或者begin>end就返回本身的位置
}
void cs(const string str)//获取下表数组
{
int max = 0;
vector<int> firste(256, -1);//hash每个字符出现位置
vector<int> laste(str.size(), -1);//储存目标下标的数组
for (int i = str.size() - 1; i >= 0; i--)
{
laste[i] = findchar(str, firste[str[i]]+1, i, str[i]);//下标数组，上一次出现的位置到当前的位置中查找 i对应的字符
firste[str[i]] = laste[i];//记录新的位置
}
//。。。
//。。。
}
如何通过数组找出这些串？
对于数组中任意位置的数。其向后遍历中的每个递减子序列（不用挨着，非严格）都对应一个回文字串！
如何读取回文串？
递减序列中，每个 对应位置原串中的字符。就是这个回文串中的一个字符。且前后对称。
例如上面的例子，对于一个递减序列。4-2-0，它出现在数组中的下标，对应原串中相应下标的字符是aba，而原串中4-2-0的 倒叙 后 作为 下标 对应字符是aba。连载一起就是aba aba。
那么问题变为了求最长递减序列，注意。不是严格递减。某些情况下递减序列中第一个值和第二个值会相等。
例如abba中。数组就是0110。最长110,递减序列第二个的值是递减序列中第一个的下标。那么回文长度是len2-2，或者说是去掉第一个的子序列10长度2.
对于abbba->01210，最长是210.递减序列中第二个的值不是第一个的下标。那么回文长度是len* 2-1.或者说是去掉一个的子序列10的长度*2+1.
经过一段时间的学习
后续步骤同leetcode300
原题是正序遍历找最长。这个反过来。倒叙 找最长。
时间复杂度oN^2,空间oN