LeetCode—— 无重复字符的最长子串

题目描述

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

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

一、CPP HashMap + 滑动窗口

解题思路：使用HashMap来记录出现的字符和其索引，在扫描过程中：

• 如果字符没有出现过，则值和索引加入map中，并更新max_length
• 如果字符已经出现过且在left右边(当前字串中)，则把left更新到之前出现过得位置（注意：left指向的是当前子串的前一个位置，计算max_length时也是使用i-left）

时间复杂度：O(n)。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int max_length = 0, left = -1, n = s.size();
        unordered_map<int, int> dict;

        for (int i = 0; i < n; ++i) {
            //出现重复，且索引位置大于left
            if (dict.count(s[i]) && dict[s[i]] > left) {
                //把索引位置更新到 i
                left = dict[s[i]];  
            }
            //不重复就记录值和索引
            dict[s[i]] = i;
            //每次都更新max_length
            max_length = max(max_length, i - left);            
        }

        return max_length;
    }
};

解法参考自：https://www.cnblogs.com/grandyang/p/4480780.html

注意：扫描最大字串时，已经扫描过的也会计算在内，比如：abcba，abc扫描完之后为b，这是再计算字串要从c开始算起，c就是之前已经扫描过的。如果扫描过之后不能再重复的话，也可以用以下方法：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int max_substring = 0;
        unordered_map<char, int> dict;
        int max_tmp = 0;

        if(s.empty())
            return 0;
        if(s.size() == 1)
            return 1;

        for(int i=0;i<s.size();i++)
        {
            if(dict.count(s[i]))
            {
                
                //比较max_tmp和max_sunstring的大小
                max_substring = max_substring >= max_tmp ? max_substring : max_tmp;
                //清空dict
                dict.clear();
                //当前加入dict
                dict[s[i]] = 1;
                //重置max_tmp
                max_tmp = 1;
            }
            else
            {
                dict[s[i]] = 1;
                max_tmp++;
            }
        }

        return max_substring;
    }
};

二、官方Java解法 set + 滑动窗口

解题思路：这个解法和上一个差不多，不同点在于这是使用的是set，set中不存在重复的元素。还一个不同点是，发生重复是，左窗口i是每次加1，知道把set中重复的元素remove掉，也就是说i是慢慢滑动的，因为其不存在索引。上面的做法直接是根据上次重复的元素的索引直接滑动。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

三、python实现（同CPP）

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        list = {}
        left = -1
        max_length = 0

        for i in range(len(s)):
            
            if s[i] in list and list[s[i]]>left:
                left = list[s[i]]

            list[s[i]] = i
            max_length = max(max_length, i-left)
    
        return max_length

四、各语言及算法时间复杂度

各语言及算法时间复杂度