LeetCode题解 #3 Longest Substring Without Repeating Characters

题目大意：给出一个字符串，找出它的所有子串中最长的满足“不包含任意重复字符”的子串。

关键字：贪心、字符串。

题目描述

解法1 - 朴素 O(n^2)

枚举子串的起点i，然后从开始枚举子串的长度l，每次往一个集合中加入最后的字符s[i+l-]，直到存在重复的字符了（利用一个Hash表来判断），这便是最大的长度。

然后在所有起点对应的最长子串中找出最长的即可。

这种解法的时间复杂度为O(n^)，难以通过。
           

解法2 - 贪心

首先我们可以稍稍修改一下解法，不再枚举子串的左端点，而是枚举子串的右端点i，不妨设右端点为i的子串，使其长度最长的左端点为l[i]。

也就是说s[l[i]..i]是一个符合要求的子串，但是s[l[i]-.i]不是一个符合要求的子串。

我们可以利用这样的信息来帮助计算l[i+]。

在枚举下一个右端点i+的时候，由于s[l[i]-.i]不是一个符合要求的子串，所以s[l[i]-.i]添加上一个s[i+]就更加不符合要求。

所以l[i+]最好情况下也就会等于l[i]，即l[i+]>=l[i]。

在枚举下一个右端点i+的时候，由于s[l[i]..i]是一个符合要求的子串，所以s[l[i]..i]添加上一个s[i+]之后得到的s[l[i]..i+]唯一可能产生重复的字符就是s[i+],所以如果s[i+]在s中上一次出现的位置是p[s[i+]]的话，我们不难发现l[i+]>=p[s[i+]]+

由于除去这样两个条件之后，没有别的条件会对l[i+]产生影响，所以我们可以知道：

l[i+]=max{l[i], p[s[i+]]+}

其中p表示的是一个字符最后一次出现的位置，是要在这个过程中进行维护的（利用一个Hash表）

由于每次计算l[i+]都是O()的，我们可以用O(n)的复杂度来求出所有的l[.n]，然后取其中最长的即可。
           

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 字符串的长度为n
        int n = s.length();
        // 用于保存上一次出现位置的hash表
        map<char, int> p;
        // 合法且长度最大的左端点位置
        vector<int> l(n);
        // 依次枚举右端点
        for (int i = ; i < n; i++) {
            if (i == ) {
                l[i] == ;
            }
            else {
                // 判断是否出现过该字符
                if (p.find(s[i]) != p.end()) {
                    l[i] = max(l[i - ], p[s[i]] + );
                }
                else {
                    l[i] = l[i - ];
                }
            }
            p[s[i]] = i;
        }
        // 求解答案
        int ans = ;
        for (int i = ; i < n; i++) {
            ans = max(ans, i - l[i] + );
        }
        return ans;
    }
};