面试题48：最长不含重复字符串的子字符串

题目见书上
暴力法可解，但超时，所以用动态规划。

/*
思路：动态规划。
f(i)表示以第i位元素结尾的不包含重复字符的子字符串的最大长度。
1.若第i个字符之前没有出现过，则f(i)=f(i-1)+1;
2.若第i个字符之前出现过，分情况讨论。令第i个字符与之前出现过的同样的字符的距离为d.
    2.1 若d<=f(i-1)，表示重复字符的前一个出现在了f(i-1)所代表的的字串中，所以f(i)=d。这也意味着第i个字符出现两次所夹的子字符串中再没有其他重复的字符。
    2.2 若d>f(i-1)，表示重复字符的前一个出现在了f(i-1)所代表的的字串以外，不影响现有不重复字符串，所以f(i)=f(i-1)+1。
*/
int lengthOfLongestSubstring(string str) {
    if (str.size() <= 0)
        return 0;
    if (str.size() == 1)
        return 1;
    int len = str.size();
    vector<int> f(len, 0);
    f[0] = 1;
    for (int i = 1; i < len; ++i)
    {
        int d = 0;
        bool duplicate = false;
        for (int j = i - 1; j >= 0; --j)
        {
            if (str[i] == str[j]&&duplicate==false)
            {
                d = i-j;
                duplicate = true;
                break;
            }
        }
        if (duplicate&&d<=f[i-1])
            f[i] = d;
        else
            f[i] = f[i - 1] + 1;
    }
    sort(f.begin(), f.end(), greater<int>());
    return f[0];
}

int main()
{
    string str = "au";
    cout << lengthOfLongestSubstring(str) << endl;
    return 0;
}

思路2：

https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/tu-jie-hua-dong-chuang-kou-shuang-zhi-zhen-shi-xia/

我们可以使用哈希表记录每个字符的下一个索引，然后尽量向右移动尾指针来拓展窗口，并更新窗口的最大长度。如果尾指针指向的元素重复，则将头指针直接移动到窗口中重复元素的右侧。

1. tail 指针向末尾方向移动；
2. 如果尾指针指向的元素存在于哈希表中：
3. head 指针跳跃到重复字符的下一位；
4. 更新哈希表和窗口长度。

   int lengthOfLongestSubstring(string str) {
    if (str.empty())
        return 0;
    map<char, int>m;
    int ret = 0, l = 0, r = 0;
    while (r<str.length())
    {
        if (m.find(str[r]) != m.end())
        {
            l = max(l,m[str[r]] + 1);
        }
        m[str[r++]] = r;
        ret = max(r - l, ret);
    }
    return ret;
   }
   

```