//牛牛参加了一个文学比赛，比赛的规则是写一段话，使得这段话中不重复的字最多，当然还要有文采。一段话的完美度就是这段话中仅出现一次的字符个数。
现在牛牛写了N段话，他想把这N段话按顺序连在一起，然后从中找出一个最短连续子串，使得这个子串的完美度最高。
输入描述： 多组测试数据，对于每组测试数据： 第一行包含一个整数N，代表牛牛写了N段话 接下来包含N段话，每段话之间中空格隔开，均有大写字母组成。 保证：1<=N<=50,1<=Ai<=50
输出描述： 对于每组数据，输出一个字符串，代表完美度最高的最长连续 子串。如果有多个，输出最早出现的子串。

#include"stdafx.h"
#include<iostream>
#include <string>
using namespace std;
//方法一穷举法
//得到一个字符串的完美度
//int getPerfectDegree(string s){
//    int length = s.size();
//    int countt = 0;//完美度,也就是不重复字符个数
//    int hashtable[256] = { 0 };
//    for (int i = 0; i<length; i++)
//    {
//        hashtable[s[i]]++;
//    }
//    for (int i = 0; i<length; i++)
//    {
//        if (hashtable[s[i]] == 1)
//            countt++;
//    }
//
//    return countt;
//}
//string getMaxSubstr(string s){
//    int length = s.size();
//    int D[2500][2500] = { 0 };
//    for (int i = 0; i<length; i++)
//    {
//        for (int j = 0; j <= i; j++)
//        {
//            D[i][j] = getPerfectDegree(s.substr(j, i - j + 1));
//        }
//    }
//    int maxx = 0;
//    int row = 0;
//    int col = 0;
//    for (int i = 0; i<length; i++)
//    {
//        for (int j = 0; j <= i; j++)
//        {
//            if (D[i][j]>maxx)
//            {
//                maxx = D[i][j];
//                row = i;
//                col = j;
//            }
//
//        }
//    }
//    cout << maxx << endl;;
//    return s.substr(col, row - col + 1);
//}
//方法二，当前结果基于前一次结果
void getMaxSubstr(string s)
{
    int a[50][50] = { 0 };
    string ans;
    int iStrlen = s.size();
    for (int i = 0; i < iStrlen; i++)
        a[i][i] = 1;
    for (int j = 1; j<iStrlen; j++)  //第j列
    {
        int index1 = -1, index2 = -1;
        for (int i = j - 1; i >= 0; i--)   //首次出现位置
        {
            if (s[i] == s[j])
            {
                if (index1 == -1)//j之前重复1次
                    index1 = i;
                else if (index2 == -1)//j之前重复多次
                {
                    index2 = i;
                    break;
                }
            }
        }

        for (int i = 0; i<j; i++)
        {
            if (i>index1)//j之前未重复
                a[i][j] = a[i][j - 1] + 1;
            else if (i>index2 && i <= index1)//j之前重复一次
                a[i][j] = a[i][j - 1] - 1;
            else//j 之前重复多次
                a[i][j] = a[i][j - 1];
        }
    }

    //for(int i=0; i<iStrlen; i++)
    //{
    //    for(int j=0; j<iStrlen; j++)
    //        cout<<a[i][j]<<" ";
    //    cout<<endl;
    //}

    int iStart = 0, iEnd = 0, iMax = 0;
    for (int j = 0; j<iStrlen; j++)
    {
        for (int i = 0; i<iStrlen; i++)
        {
            if (a[i][j]>iMax)
            {
                iMax = a[i][j];
                iStart = i;
                iEnd = j;
            }
        }
    }

    ans = s.substr(iStart, iEnd - iStart + 1);
    cout << a[iStart][iEnd] << endl;
    cout << ans << endl;

}
int main(){
    string s = "hello";
    // cout<<s.substr(0,5);从0开始5个

    /*cout << getMaxSubstr(s);*/
    getMaxSubstr("aohhad");
    return 0;
}