leetcode 3. 最长不含重复的子字符串的五种解法

leetcode链接：最长不含重复的子字符串

题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 

解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: s = "bbbbb"
输出: 1

解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = "pwwkew"
输出: 3

解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
示例 4:

输入: s = ""
输出: 0

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

方法一

这道题可以用动态规划来解，思路解析：https://zhuanlan.zhihu.com/p/80538556

AC代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty())   return 0;
        int cur_len = 0;
        int max_len = 0;
        int tmp = -1;
        std::map<char, int> lastindex;
        for(auto i = 0; i < s.length(); i++)
        {
            if(lastindex.find(s[i]) == lastindex.end()) // not found
            {
                cur_len++;

            }
            else
            {
                tmp = i - lastindex[s[i]];
                if(tmp > cur_len)
                {
                    cur_len++;

                }
                else
                {
                    cur_len = tmp;

                }
            }
            max_len = max(max_len, cur_len);
            lastindex[s[i]] = i;
        }
        return max_len;
    }
};

方法二

思路解析：利用 hashset 来检查重复元素。

• 我们定义 l 和 r 两个指针表示一个特定的子字符串的首和尾。初始它们都在索引 0 处。

• 移动 r，并同时向 hashset 中添加 r 所指的元素值，当 r 指到重复的元素时，r - l 的值就是一个不含重复字符的子字符串的长度。

• erase 掉 haseset 中的 l 所指元素的值，然后让 l++（for 循环的作用）。之后继续移动 r来找到下一个不含重复字符的子字符串的长度。

AC代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size()==0) return 0;
        unordered_set<char> store;
        int res=-1;
        int l=0,r=0;
        for(l=0;l<s.size();l++)
        {
            while(r<s.size()&&!store.count(s[r]))//set的count值只能是0或1
            {
                store.insert(s[r]);
                r++;
            }
            res=max(res,r-l);
            store.erase(s[l]);
            if(r>=s.size()) break;
        }
        return res;
    }
};

但因为涉及到频繁的元素erase，这个耗时会比第一种方法略高。

方法三

思路解析：使用滑动窗口来做。
窗口的范围为 [left, right]，left，right初始化为0。
设置一个查找表 lookup，lookup 存储了当前窗口中的元素。right 先移动，如果 s[right] 不在 lookup 中，则 right++，maxLen++，将 right 加入 lookup 中；否则，将 s[left] 从 lookup 中移除（注意这里不是先移除重复的元素 s[right]，因为先移除 s[right] 的话就不满足连续子串这个要求了），将 left++，直至 s[right] 不在 lookup 中出现。当遇到了重复字符，我们一步一步地移动 left 指针。为了加快速度，我们可以直接将 left 移动到当前 right 的位置上。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty()) return 0;
        vector<int> v(128, -1);
        int left = -1;
        int maxLen = 1;
        for(int right=0; right<s.size(); right++){
            char c = s[right];
            if(v[c]!=-1) left = max(left, v[c]);   // c 出现在了窗口中
            v[c] = right;
            maxLen = max(maxLen, right-left);
        }
        return maxLen;
    }
};

方法四
双指针，可以直接看代码和注释：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (!s.size()) return 0; // 判空
        int maxLength = 0; // 记录最长不包含重复字符的子字符串的长度
        int left = 0, right = 0; // 初始化双指针
        unordered_set<char> subStr; // 哈希表存储不包含重复字符的子串
        /*
        *  双指针遍历原字符串:
        *  外层左指针、内层右指针
        */
        while (left < s.size()) {
            /*
            *  右指针不断右移遍历字符串
            *  当遇到的字符在哈希表中不存在时，将其插入哈希表
            *  遇到哈希表中存在的字符 或 到原字符串结尾时跳出循环
            */
            while (right < s.size() && !subStr.count(s[right])) {
                subStr.insert(s[right]);
                right++;
            }
            /*
            *  更新最大子串的长度
            *  因为上面的循环跳出时right指向的是子串后面一个位置
            *  所以是right-left而不是right-left+1
            */
            maxLength = max(maxLength, right - left);
            /*
            *  若上面循环跳出是因为右指针到原字符串末尾，
            *  说明遍历完毕，最长不包含重复字符的子串已经找到
            *  直接跳出循环
            */
            if (right == s.size()) break;
            /*
            *  若上面循环跳出是因为遇到了哈希表中已有的字符
            *  则从左边开始挨个删除哈希表中的字符
            *  并且左指针右移
            */
            subStr.erase(s[left]);
            left++;
        }
        return maxLength;
    }
};

方法五

背包

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> vec(128);
        int res = 0, beg = 0, len = s.size();
        for(int i = 1; i <= len; ++i) {
            auto &x = vec[s[i-1]];
            if(beg < x) { beg = x; }
            if(res < i - beg) { res = i - beg; }
            x = i;
        }
        return res;
    }
};