3_12最长无重复字符子串

对于一个字符串,请设计一个高效算法，找到字符串的最长无重复字符的子串长度。

给定一个字符串A及它的长度n，请返回它的最长无重复字符子串长度。保证A中字符全部为小写英文字符，且长度小于等于500。

测试样例：
输入："aabcb",5
返回：3

class DistinctSubstring {
    public:
        int longestSubstring(string A, int n) {
            // write code here
            // 用数组（初始化为-1）记录每个字符前一次出现的位置，如果数组中该字符索引的位置不为-1，
            // 则说明出现重复，
            vector<int> dict(256, -1);
            // idx表示当前字符的位置，start指向开始计算长度的起始点，start之前的全部抛弃
            int idx = 0, longest = 0, start = 0;
            while(idx < n){
                // 不重复，长度+1， 并记录当前出现的位置
                if(-1 == dict[A[idx]]){
                    dict[A[idx]] = idx; 
                    longest = max(idx - start + 1, longest);
                }else{
                    // 出现重复，判断当前字符A[idx]之前出现的位置和start谁更靠右，
                    // 然后求出当前位置往前的最大无重复长度
                    int dist = min(idx - dict[A[idx]], idx - start +1);
                    longest = max(dist, longest);
                    start = max(dict[A[idx]]+1, start);
                    cout << start << '\n';
                    dict[A[idx]] = idx;
                }
                ++idx;            
            }
            return longest;
        }
};