牛客网编程题-超级子串

     题目如下：

分析：

刚开始看到这个题的时候就懵了，完全没有思路，后来经过分析有如下想法。

       首先，这道题和我们的求字符串的最长无重复子串不同，因为最长无重复子串要求满足条件的字符串区间内没有重复的字符，但是这个题目满足条件的字符串区间可以有重复的子串，如图有如下情况：

HGSFKGHFMNOPQGABCDEGHIK

我们看到红色部分是最佳的满足条件的子串，尽管这个子串含有重复的字符，因为这个题目满足这样的逻辑：

假设有字符串如下

a1a2a3a4a5a6a4a8a9a10

假设a1到a6之间没有重复的字符，但是接下来有个重复的字符a4,这个时候如果把a4加入到已有的未重复字符串中且当前子串的总长度为6，但是这个时候我们如果从新a4开始从新计算的话得到值是4(即a4a8a9a10),那么和前面的6比较得到满足条件的子串是a1a2a3a4a5a6。但事实是这样的吗？

如果我们将a4继续累加，虽然总长度增加1变成7，但是【a1a2a3a4a5a6a4】之间的无重复字符的个数确变成7-2=5个，好像比之前说过的六个还要少，这个好像不行？但是当我们继续累加直到整个字符串结束，得到的结果是8.这个子串才是最符合条件的。

到这里我们不由得想到了动态规划算法，基本思想是计算每两个字符之间(包含两个端点字符)构成子串的完美度,然后将他们记录在一张n×n的表格中

具体代码如下：

class mysolution{
public:
	pairTheMostPerfectSubstring1(string s) {//动态规划法
		int len = 0,j,now=0,size=s.size();//具有最大完美度的字符子串中无重复字符的个数
		pairresult;
		vectort(size,0);
		vector>p;
		for (int i = 0; i len){
				len = p[0][i];
				result.first = 0;
				result.secOnd= i;
			}
			arr[s[i] - 65]++;
			memcpy(tmp,arr,26*sizeof(int));
			for(j = 0; jlen){
					len = p[j+1][i];
					result.first = j+1;
					result.secOnd= i;
				}
			}
		}
		return result;
	}
};

思想描述：

使用二维容器是为了方便调试p中的内容，在上面的代码中我们主要利用了两点：

1.在p的第一行中，我们保存了截至到目前为止的无重复字符的个数，同时用arr数组来保存截至当前每个字符出现的个数；

2.在求解的过程中我们利用第一行的(截至到目前为止无重复出现字符的个数)值来反向推倒，假设有如下的例子：

IAMAGO ODBOYTA MGDBSKH

将中间的空格处理之后就是

IAMAGOODBOYTAMGDBSKH

那我们的表格的第一行就是：

那么字母下面的数字就是代表截至目前为止无重复字符的个数,现在我们得到了p的第一行，那么我们怎样得到p的第二行呢？过程是这样的：

以如下分支为例：

我们知道p[1][4]=2,代表从第1个字符到第4个字符的无重复字符个数为2,那么p[2][4]怎么求，理论上很简单，就是要去掉第一字符，第1个字符有如下几种情况：

A.第1个字符只出现1次

那么我们将这个字符拿掉的时候，p[2][4]无重复字符的数量肯定要-1；

B.第1个字符刚好出现2次

如果刚好出现两次，那我们把第1个拿掉的时候，这个字符剩下出现的次数变成1(代表无重复出现了)，那么无重复字符的个数要+1；

C.第1个字符出现3次以上

如果该字符，那么该字符的剩余个数大于等于2，这个时候对无重复字符的个数毫无影响(这个逻辑要想清楚)；

那么这个过程的动态规划过程就是：

p[j+1][i] = p[j][i] - 1;

p[j+1][i] = p[j][i] + 1;

                                                                                                                                          p[j+1][i] = p[j][i];

P[j+1][i]表示从下标j+1开始到下标i截至字符出现的无重复字符的个数，P[j][i]表示从下标j开始到下标i截至字符出现的无重复字符的个数，整个算法的精髓就在两点：

1.首先求出第1行中截至到目前为止无重复字符出现的个数以及截至当前每个字符出现的次数；

2.利用上述的动态规划递推式至上而下将p中的每一行数据填满，这样，从任意点i到j之间的无重复出现字符的个数就全部记录在二维容器p中；

测试结果：