/*

题目：

	最长不含重复字符的子字符串。

*/

/*

思路：

	f(i) = f(i-1) + 1,(未出现过当前字符，distance > f(i-1)

		   distance，当前字符和上一次出现该字符的距离

*/

#include<iostream>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

int longestSubstringWithoutDuplication(string str){

    int en[26];

    memset(en,-1,sizeof(en));

    int len = str.size();

    int maxVal = 0;

    int curr = 0;

    for(int i = 0; i < len; i++){

        if(en[str[i]-'a'] == -1){

            curr = curr + 1;

        }else{

            int d = i - en[str[i]-'a'];

            if(d > curr){

                curr++;

            }else{

                if(curr > maxVal){

                    maxVal = curr;

                }

                curr = d;

            }

        }

        cout<<str[i]<<" "<<i<<" "<<curr<<endl;

        en[str[i]-'a'] = i;

    }

    return max(curr,maxVal);

}

int main(){

    string str="arabcacfr";

    cout<<longestSubstringWithoutDuplication(str);

    return 0;

}