【Day 22 】2022-01-02 - 3. 无重复字符的最长子串

[azl397985856]

3. 无重复字符的最长子串

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

前置知识

• 哈希表
• 双指针

  题目描述

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

示例 1:

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

示例 2:

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

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

[CodingProgrammer]

思路

滑动窗口，每个滑动窗口内的子字符串的字符都是不重复的。具体地：

• 右指针从 0 开始，一直向右滑动，每遍历到一个字符，就将 count 中对应的位置加 1；
• 当发现某个字符的数量大于 1 的时候，说明有重复字符，那么左指针开始向右滑动从而缩小窗口，在缩小滑动窗口的同时也需要将 count 中对应字符的数量减 1
• res 记录滑动窗口的全局最大值

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int[] count = new int[128];
        char[] chs = s.toCharArray();
        int length = chs.length;
        int res = 0, left = 0;
        // 右指针一直向右滑动
        for (int right = 0; right < length; right++) {
            // 右指针每到一个新的位置，先将该位置对应字符的数量加 1
            int countRight = chs[right] - ' ';
            count[countRight]++;
            // 如果某个字符的数量大于1，开始移动左指针，缩小窗口使得大于 1 的字符的数量恢复到1
            while (count[countRight] > 1) {
                int countLeft = chs[left++] - ' ';
                count[countLeft]--;
            }
            res = Math.max(res, right - left + 1);
        }

        return res;
    }
}

复杂度

• Time : O(N)
• Space: O(C) C = 128

[L-SUI]

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const length = s.length
    const map = new Map();
    let i=0,
        j=0;
    let ans = 0;
    while (i<length && j<length) {
        if (map.has(s[j]) && map.get(s[j])>=i) {
            i=map.get(s[j])+1
        }
        ans = Math.max(j-i+1,ans)
        map.set(s[j],j);
        ++j;
    }
    return ans
};

[Myleswork]

思路

滑动窗口+hash

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> hash;
        int left = 0;
        int maxlen = 0;
        for(int right = 0;right<s.length();right++){
            if(hash.find(s[right]) != hash.end()){
                //说明是有的,left往后走到直到right在前面没有为止
                while(hash.find(s[right]) != hash.end()) hash.erase(s[left++]);
            }
            hash.emplace(s[right]);
            maxlen = maxlen>hash.size() ? maxlen:hash.size();
        }
        return maxlen;

    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

[1052561252]

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0, start = 0; end < n; end++) {
            char alpha = s.charAt(end);
            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }
            ans = Math.max(ans, end - start + 1);
            map.put(s.charAt(end), end + 1);
        }
        return ans;
    }
}

[tongxw]

思路

滑动窗口，窗口内用HashSet来检查是否有重复字符。

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
      Set<Character> set = new HashSet<>();
      int l = 0;
      int ans = 0;
      for (int r=0; r<s.length(); r++) {
          char c = s.charAt(r);
          while (set.contains(c)) {
              set.remove(s.charAt(l));
              l++;
          }

          ans = Math.max(ans, r - l + 1);
          set.add(c);
      }

      return ans;
    }
}

SC: O(N) TC: O(N)

[last-Battle]

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        int start = 0, end = 0;

        unordered_map<int, int> um;
        for (; end < s.length(); ++end) {
            if (um.find(s[end]) != um.end()) {
                start = um[s[end]] + 1;
                um.erease(um[s[end]]);
            }
            um[s[end]] = end;

            cout << s[end] << ", start:" << start << ", end:" << end << endl;

            res = max(res, end - start + 1);
        }

        return res;
    }
};

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[biscuit279]

思路

滑动窗口，遇到已经出现的元素就移动窗口

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        max_len, current_len, l, r = 0, 0, 0, 0
        posi_dict = {}
        while r < n:
            char = s[r]
            if char in posi_dict and posi_dict[char]>=l:
                l = posi_dict[char] + 1
            posi_dict[char] = r
            current_len = r-l+1
            max_len = max(max_len, current_len)
            r += 1
        return max_len

时间复杂度：O（N） 空间复杂度：O（s）

[haixiaolu]

思路

滑动窗口 + 集合

• 定义一个集合
• 定义一个左指针和右指针
• 左指针的起点为0， 右指针遍历每个字符串的字符
• 如果右指针遍历到的字符已经出现在set 中
  • remove 最左边的字符
  • 更新左指针
• 如果右指针遍历到的字符没有出现在set中
  • add右指针遍历到的当前字符
• 取最大的长度

代码 / Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        left = 0
        result = 0

        # right pointer go through every character in string
        for right in range(len(s)):
            # if right pointer visited char is already in the set, it means we have a duplicates
            while s[right] in charSet:
                # update window since there is a duplicate
                charSet.remove(s[left]) # remove the most left char
                left += 1

            charSet.add(s[right]) # add right char to the set 
            result = max(result, right - left + 1)

        return result 

复杂度分析

• 时间复杂度： O(n)
• 空间复杂度: O(n)

[tangjy149]

思路

滑动窗口，应用双指针专题中的模板进行。
具体使用hashtable进行存储每个字符出现次数，如果出现快指针的字符出现次数大于1，则移动慢指针，并使hashtable中的慢指针的字符减1，直到出现快指针的字符出现次数=1

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> helper;
        int ans=0;
        int slow=0;
        for(int i=0;i<s.size();i++){
            helper[s[i]]++;
            while(helper[s[i]]>1){
                helper[s[slow]]--;
                slow++;
            }
            ans=max(ans,i-slow+1);
        }
        return ans;
    }
};

复杂度

时间复杂度：O（n） 空间复杂度：O（n）(哈希表的空间)

[JudyZhou95]

思路

滑动窗口+hashmap。维护滑动窗口，保证窗口里没有重复的字母。具体做法是，用两个指针，p1作为窗口入口，p2用来遍历，每次遍历到的字母加入hashtable中，如果发现之前出现过重复的（可能在当前窗口，可能在更前面），就比较p1和之前的index，如果index出现在p1之前就不用移动p1，如果在p1之后就要把p1移到该index后面。

代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) <= 1:
            return len(s)

        ind_table = dict()        
        p1 = p2 = 0

        l = len(s)
        max_len = 0

        while p1 <= p2 and p2 < l:
            if s[p2] in ind_table:
                p1 = max(p1, ind_table[s[p2]]) #如果该字母在p1之前出现，就跳过了p1不会移动

            ind_table[s[p2]] = p2+1
            max_len = max(max_len, p2-p1+1)
            p2+=1
        return max_len

复杂度

TC: O(N)

SC: O(N)

[Moin-Jer]

思路

---

滑动窗口

代码

---

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        char[] cs = s.toCharArray();
        int n = cs.length;
        int l = 0, r = 0, ans = 0;
        while (r < n) {
            if (!set.contains(cs[r])) {
                set.add(cs[r]);
                ++r;
            } else {
                ans = Math.max(ans, r - l);
                while (set.contains(cs[r])) {
                    set.remove(cs[l]);
                    ++l;
                }
                set.add(cs[r]);
                ++r;
            }
        }
        ans = Math.max(ans, r - l);
        return ans;
    }
}

复杂度分析

---

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[z1ggy-o]

思路

string 中的每一个 char 都可以成为 substring 的起始点。 只需要知道每个 substring 的长度，就可以求得结果。

简单的 loop 会重复访问，出现不必要的浪费，使得复杂度为 O(n^2). 通过使用滑动窗口，我们可以避免重复访问，使得复杂度降低。 （每个循环，窗口左侧是新的起始点，右侧是至今还没出现重复字母的位置）

代码

CPP

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 0 || s.size() == 1)
            return s.size();

        unordered_set<char> existed;
        int len = 0;
        int end = -1;
        for (int i = 0; i < s.size(); i++) {
            // move string end idx; check repeat char
            while (end + 1 < s.size() && !existed.count(s[end + 1])) {
                existed.insert(s[end+1]);
                end++;
            }
            len = max(len, end - i + 1);

            if (end + 1 == s.size()) {  // all chars are checked
                break;
            }
            existed.erase(s[i]);  // new substring starts by s[i+1]
        }
        return len;   
    }
};

复杂度分析

• 时间：O(n), 一个字母最多被访问两次
• 空间：O(n), 最差情况，所有的字母都是不同的

[Leonalhq]

class Solution(object): def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """

need set for non-repeating

# need 2 pointer to maintain the window
# a counter to memerize the max length
# return B-A+1
    size = len(s)
    if size < 1:
        return size
    maxs = 1
    # if dupicate -> left + 1
    # else right keep goin till end of the string
    # loop until left till the end of string
    for i in range(size):
        dic = {str(s[i])}
        for j in range(i+1,size):
            if str(s[j]) in dic:
                break
            else:
                dic.add(str(s[j]))
        maxs = max(maxs,len(dic))
    return maxs

[uniqlell]

public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int maxLen = 0;//用于记录最大不重复子串的长度
        int left = 0;//滑动窗口左指针
        for (int i = 0; i < s.length() ; i++)
        {
            /**
            1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,
             此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；

            2、如果当前字符 ch 包含在 map中，此时有2类情况：
             1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，
             那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；
             2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，
             而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0；
             随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时
             应该不变，left始终为2，子段变成 ba才对。

             为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).
             另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，
             因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！
             */
            if(map.containsKey(s.charAt(i)))
            {
                left = Math.max(left , map.get(s.charAt(i))+1);
            }
            //不管是否更新left，都要更新 s.charAt(i) 的位置！
            map.put(s.charAt(i) , i);
            maxLen = Math.max(maxLen , i-left+1);
        }

        return maxLen;
    }

[didiyang4759]

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
        }
        return max;  
    }
}

[junbuer]

思路

• 滑动窗口

  代码

  class Solution(object):
  def lengthOfLongestSubstring(self, s):
      """
      :type s: str
      :rtype: int
      """
      hashmap = set()
      r, max_len = -1, 0
      for l in range(len(s)):
          if l != 0:
              hashmap.remove(s[l-1])
          while r + 1 < len(s) and s[r + 1] not in hashmap:
              hashmap.add([s[r + 1]] )
              r += 1
          max_len = max(max_len , r - l + 1)
      return max_len

  复杂度分析

• 时间复杂度：$O(n)$

• 空间复杂度：$O(m)$，m为hash表的长度

[732837590]

class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0; Map<Character, Integer> map = new HashMap<>(); for (int end = 0, start = 0; end < n; end++) { char alpha = s.charAt(end); if (map.containsKey(alpha)) { start = Math.max(map.get(alpha), start); } ans = Math.max(ans, end - start + 1); map.put(s.charAt(end), end + 1); } return ans; } }

[ginnydyy]

Problem

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Note

• two pointers and set

Solution

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.isEmpty()){
            return 0;
        }

        int max = 0;
        Set<Character> set = new HashSet<>();
        int left = 0;
        int right = 0;

        while(right < s.length()){
            if(set.contains(s.charAt(right))){
                max = Math.max(right - left, max);
                while(set.contains(s.charAt(right)) && left < right){
                    set.remove(s.charAt(left));
                    left++;
                }
            }else{
                set.add(s.charAt(right));
                right++;
            }
        }

        max = Math.max(max, right - left);

        return max;

    }
}

Complexity

T: O(n). n is the length of s. S: O(n).

[YuyingLiu2021]

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res = []
        l = 0
        for i in s:
            while i in res:
                res.pop(0)
            res.append(i)

            if len(res) > l:
                l = len(res)
        return l

[Tesla-1i]

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        ans = 1
        i, j = 0, 0
        lastSeen = {}
        while j < len(s):
            if s[j] in lastSeen and i < lastSeen[s[j]]:
                    i = lastSeen[s[j]]
            lastSeen[s[j]] = j + 1
            ans = max(ans, j -i + 1)
            j += 1
        return ans

[ywang525]

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: from collections import defaultdict lookup = defaultdict(int) start = 0 end = 0 max_len = 0 counter = 0 while end < len(s): if lookup[s[end]] > 0: counter += 1 lookup[s[end]] += 1 end += 1 while counter > 0: if lookup[s[start]] > 1: counter -= 1 lookup[s[start]] -= 1 start += 1 max_len = max(max_len, end - start) return max_len

[simbafl]

这道题，每次都那么熟悉，结果每次都得看答案

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        from collections import defaultdict
        lookup = defaultdict(int)
        start = 0
        end = 0
        counter = 0
        max_len = 0
        while end < len(s):
            if lookup[s[end]] > 0:
                counter += 1
            lookup[s[end]] += 1
            end += 1
            while counter > 0:
                if lookup[s[start]] == 2:
                    counter -= 1
                lookup[s[start]] -= 1
                start += 1
            max_len = max(max_len, end-start)
        return max_len

[1149004121]

3. 无重复字符的最长子串

思路

无重复考虑用哈希表保存遍历过的每个字符，考虑用2个指针分别指向无重复子串的头和尾，如果右指针碰到重复的，将左指针指向该字符上一次出现的位置的后面并将哈希表中前面的字符抛出。

代码

    var lengthOfLongestSubstring = function(s) {
        let map = new Map();
        let left = 0, right = 0;
        let res = 0;
        const len = s.length;
        while(right <= len - 1){
            if(!map.has(s[right])){
                map.set(s[right], right);
            }else{
                res = Math.max(right - left, res);
                left = map.get(s[right]) + 1;
                for(let char of map.keys()){
                    if(char === s[right]){
                        map.delete(char);
                        break;
                    }else{
                        map.delete(char);
                    } 
                }
                map.set(s[right], right);
            }
            right++;
        }
        return Math.max(right - left, res);
    };

复杂度分析

• 时间复杂度：O(N)。
• 空间复杂度：O(N)。

[arteecold]

说是说确实是滑动窗口老经典了。。。但是很难每次及时get点

[Hacker90]

思路

滑动窗口，窗口内的都是没有重复的字符，我们需要尽可能的扩大窗口的大小。由于窗口在不停向右滑动， 所以我们只关心每个字符最后出现的位置，并建立映射。窗口的右边界就是当前遍历到的字符的位置 ，为了求出窗口的大小，我们需要一个变量left来指向滑动窗口的左边界，这样，如果当前遍历到的字符从未出现过， 那么直接扩大右边界，如果之前出现过，那么就分两种情况，在或不在滑动窗口内，如果不在滑动窗口内，那么就没事， 当前字符可以加进来，如果在的话，就需要先在滑动窗口内去掉这个已经出现过的字符了，去掉的方法并不需要将左边界left 一位一位向右遍历查找，由于我们的HashMap已经保存了该重复字符最后出现的位置，所以直接移动left指针就可以了。 我们维护一个结果res，每次用出现过的窗口大小来更新结果res，就可以得到最终结果了

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int pleft = 0;
        int pright = 0;
        int res = INT_MIN;
        int size = s.size();
        if(s.empty())return 0;
        if(size == 1)return 1;
        unordered_map<char,int> map;
        while(pright < size){

            if(map.find(s[pright])!= map.end()) {  
                cout<<s[pleft]<<"["<<endl;
                map.erase(s[pleft]);     ////找到重复的，减少窗口左边，左边界向右移动且删除，直到窗口内没有存在与当前右窗口最新遍历一样的键值
                pleft++;              
            }else {     //没有重复的，扩大窗口右边
            cout<<s[pright]<<"]"<<endl;
                map[s[pright]] = pright;  
                pright++;   
                res = max(res,(int)map.size());
            }
        }

        return res;
    }
};

复杂度分析

• 时间复杂度：O(n)，
• 空间复杂度：O(n)

[ZZRebas]

思路

遍历

代码(Python)

def fun(in_str):
    no_re=""
    max_len=0
    for c in in_str:
        if c not in no_re:
            no_re+=c
        else:
            if max_len<len(no_re):
                max_len=len(no_re)
            no_re=c
    print(max_len)

# in_str="abcabcbb"
# in_str="bbbbb"
in_str="pwwkew"
fun(in_str) #3

复杂度分析

• 时间复杂度： O(N)，N为字符串长度。
• 空间复杂度：

[zwx0641]

class Solution { public int lengthOfLongestSubstring(String s) { Map<Character, Integer> map = new HashMap<>(); int i = 0, j = 0, ans = 0; for (; j < s.length(); j++) { char c = s.charAt(j); while (map.getOrDefault(c, 0) != 0) { map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) - 1); i++; } map.put(c, map.getOrDefault(c, 0) + 1); ans = Math.max(ans, j - i + 1); } return ans; } }

[samaritan1998]

最长无重复子串

• 滑动窗口思想

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cur=set()
        n=len(s)
        ans=0
        left,right=0,0
        while right<n:
            while s[right] in cur:
                cur.remove(s[left])
                left+=1
            cur.add(s[right])
            ans=max(ans,len(cur))
            right+=1
        return ans

[aladingzl]

思路

利用滑动窗口，维护一个最大值

代码

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let set = new Set();
    let result = 0;
    for(let i = 0, j = 0; i < s.length; i++) {
        while(set.has(s[i])) {
            set.delete(s[j++]);
        }
        set.add(s[i]);
        result = Math.max(result, set.size);
    }
    return result;
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[lilililisa1998]

def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ ''' 有一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，把队列的左边的元素移出，直到满足题目要求.一直维持这样的队列，找出队列出现最长的长度时候，求出解！ ''' if not s:return 0 left = 0 lookup = set() n = len(s) max_len = 0 cur_len = 0 for i in range(n): cur_len += 1 while s[i] in lookup: lookup.remove(s[left]) left += 1 cur_len -= 1 if cur_len > max_len:max_len = cur_len lookup.add(s[i]) return max_len

[Richard-LYF]

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: k, res, c_dict = -1, 0, {} for i, c in enumerate(s): if c in c_dict and c_dict[c] > k: # 字符c在字典中 且 上次出现的下标大于当前长度的起始下标 k = c_dict[c] c_dict[c] = i else: c_dict[c] = i res = max(res, i-k) return res

# on osigma

[callmeerika]

思路

利用双指针和Map，Map记录字符-位置，右指针每次挪一格，而左指针则是在碰到重复字符的时候，跳到该字符上次出现的位置的下一个位置

代码

var lengthOfLongestSubstring = function(s) {
    if(!s) return 0;
    let length = [];
    let str = s.split('');
    let hash = new Map();
    let p = 0;
    let q = 0;
    while(q<str.length) {
        let temp = hash.get(str[q]);
        if(temp!==undefined && temp >= p) {
            length.push(q-p);
            p = hash.get(str[q]) + 1;
            hash.set(str[q],q)
        } else {
            hash.set(str[q],q)
        }
        q = q + 1;
    }
    length.push(q-p);
    return Math.max(0,...length)
};

复杂度

时间复杂度：O(n)
空间复杂度：O(n)

[luhnn120]

思路

通过哈希表来记录重复字符串。通过双指针构成滑动窗口，快指针遍历字符串，当前字符哈希表中不存在时添加到哈希表中，继续遍历。当前字符哈希表中存在时则移动慢指针收缩窗口直到慢指针找到相同的字符串。

代码

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  if (!s) {
    return 0
  }
  let max = 1, set = new Set(), j = 0;
  set.add(s[j]);
  for (let i = 1; i < s.length; i++) {
    if (set.has(s[i])) {
      while (s[j] !== s[i]) { 
        set.delete(s[j])
        j++
      }
      j++
    } else { 
      set.add(s[i])
      max = Math.max(set.size, max)
    }
  }
  return max;
};

复杂度

时间复杂度：O(n) n为字符串长度 空间复杂度：O(m) m为字符串中不重复字符基长度

[noperoc]

思路

• 哈希表记录已经出现过的字符，双指针，一个指开头，一个指现在，现在的如果前面出现了，前面的指针就一直往后走，直到不重复，同时记录当前的字符串长度，维护最长的答案

关键点

代码

• 语言支持：Java

Java Code:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        char[] chars =s.toCharArray();
        int ans = 0;
        int best = 0;
        int start_index = 0;
        for(char cs:chars){
            while(map.containsKey(cs)){
                char tmp = chars[start_index];
                map.remove(tmp);
                start_index += 1;
                ans -=1;
            }
            map.put(cs, 1);
            ans+=1;
            best = best > ans ? best : ans;
        }
        return best;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[dudongli]

class Solution: def lengthOfLongestSubstring(self, s: str) -> int:

    dic, res, i = {}, 0, -1   #i是左指针
    for j in range(len(s)):  #j是右指针
        if s[j] in dic:     #若当前元素在之前出现过，更新左指针
            #当之前出现的元素在左右指针中间，左指针更新为之前元素下标，若不在中间，左指针不变
            i = max(i, dic[s[j]]) 
        dic[s[j]] = j    #将当前元素加入哈希表中
        res = max(res, j - i)   
    return res

[Size-of]

var lengthOfLongestSubstring = function(s) { let left = 0 const list = s.split('') const map = new Map() let res = 0 for(let right = 0; right < list.length; right++) { map.set(list[right], (map.get(list[right]) || 0) + 1) while(map.get(list[right]) > 1) { map.set(list[left], map.get(list[left]) - 1) left++ } if (res < right - left + 1) { res = right - left + 1 } } return res };

[MissNanLan]

暴力法

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {string} s
 * @return {number}
 */
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    let res = 0;
    for (let i = 0; i < s.length; i++) {
      let map = {};
      for (let j = i; j < s.length; j++) {
        if (map[s[j]] !== undefined) {
          break;
        }
        map[s[j]] = true;
        res = Math.max(res, j - i + 1);
      }
    }
    return res;
  };

复杂度分析

令 n 为数组长度。

• 时间复杂度: O(n^2)

• 空间复杂度: O(s), s为字符集元素个数

[rootdavid]

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
      int res = 0;
      unordered_map<char, int> map;

      for (int i = 0, j = 0; i < s.size(); i++) {
        map[s[i]]++;

        while (map[s[i]] > 1) map[s[j++]]--;

        res = max(res, i - j + 1);

      }

      return res;
    }
};

[Macvh]

def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ if not s:return 0 left = 0 lookup = set() n = len(s) max_len = 0 cur_len = 0 for i in range(n): cur_len += 1 while s[i] in lookup: lookup.remove(s[left]) left += 1 cur_len -= 1 if cur_len > max_len:max_len = cur_len lookup.add(s[i]) return max_len

[chenyaohn]

思路

由题可知，可用滑动窗口求解。
定义滑动窗口左坐标l,遍历字符串，每次遍历判断滑动窗口中是否有当前正在遍历的字符，如果有则l+1。每次遍历完毕后更新不重复字符串长度。

代码

public class Day22 {

    public int lengthOfLongestSubstring(String s) {

        int maxSize=0;
        int l =0 ;
        int firstIndex;
        for (int i = 0; i < s.length(); i++) {
            firstIndex = s.indexOf(s.charAt(i),l);
            if(firstIndex<i) {
                l = firstIndex+1;
            }
            maxSize = i-l+1>maxSize?i-l+1:maxSize;

        }
        return maxSize;
    }
}

复杂度分析

时间复杂度：O(NlogN) 这里调用了String的index()方法(其复杂度应为O(logN))
空间复杂度：O(1)

[revisegoal]

滑动窗口

• 每次迭代，判断哈希表是否包含s[r]，若包含则移除s[l]，l右移
• 将s[r]加入哈希表中，并更新ans，r右移

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        // hashmap是用键索引，hashset是比较hashCode值，所以用hashmap更快
        Map<Character, Boolean> map = new HashMap<>();
        int l = 0, r = 0, ans = 0;    
        while (r < n) {
            while (map.containsKey(s.charAt(r))) {
                map.remove(s.charAt(l));
                ++l;
            }
            map.put(s.charAt(r), true);
            ans = Math.max(ans, r - l + 1);
            ++r;
        }
        return ans;
    }
}

复杂度

• 时间：O(n)，n为s长度
• 空间：O(C)，C为字典集大小

[declan92]

思路：
使用哈希表key保存字符串索引,value保存最长子串;
如果第i位字符不在i-1最长子串中,则最长子串为sub(i-1)+s.charAt(i);
如果在i-1最长子串中,求出其索引截断,然后与s.charAt(i)拼接;
步骤:

1. 字符串为""时,返回0;
2. 遍历字符串,判断s.charAt(i)是否在哈希表key = i-1对应的值中;
3. 不在,则f(i)=f(i-1) + 1;在则f(i) = f(i-1);
4. 使用打擂台方式保存最大长度; java

   class Solution {
   public int lengthOfLongestSubstring(String s) {
       int ans = 0;
       Map<Integer, String> map = new HashMap();
       if (s.equals("")) {
           return 0;
       }
       for (int i = 0; i < s.length(); i++) {
           Character c = s.charAt(i);
           String cs = c.toString();
           if (i == 0) {
               map.put(i, cs);
           } else {
               String sub = map.get(i - 1);
               if (!sub.contains(cs)) {
                   map.put(i, sub + c);
               } else {
                   int j = sub.indexOf(c);
                   if (j == sub.length() - 1) {
                       map.put(i, cs);
                   } else {
                       map.put(i, sub.substring(j + 1) + c);
                   }
               }
           }
           ans = Math.max(ans, map.get(i).length());
       }
       return ans;
   }
   }

   时间:O($n^2$),循环遍历字符串n次,sub.contains()方法也是O(n)级别;
   空间:O(n);

[CodeWithIris]

Question

Day22 3
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

Note (Hash table, Sliding window)

• Use unordered_map to store the char and the last position.
• Once the repeating alpha appears, update the start position of the sliding window.

Solution (C++)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size(), ans = 0, start = 0;
        unordered_map<char,int> mp;
        for(int i = 0; i < n; ++i){
            if(mp.count(s[i])){
                start = max(mp[s[i]] + 1, start);
            }
            ans = max(ans, i - start + 1);
            mp[s[i]] = i;
        }
        return ans;
    }
};

Complexity

• T: O(n)
• S: O(k): K is the number of different elements of the string.

[stackvoid]

思路

HashSet + 两层循环解决。

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {

        if (s == null || s.length() == 0) return 0;
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            HashSet<Character> set = new HashSet<>();
            int curAns = 1;
            set.add(s.charAt(i));
            for (int j = i + 1; j < s.length(); j++) {
                if (set.contains(s.charAt(j))) {
                    break;
                } else {
                    curAns++;
                    set.add(s.charAt(j));
                }
            }
            if (ans < curAns) {
                ans = curAns;
            }
            set.clear();
            curAns = 1;

        }
        return ans;
    }
}

算法复杂度分析

• 时间复杂度： O(N^2)
• 空间复杂度：O(N)

[15691894985]

day22】 3. 无重复字符的最长子串

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

方法：哈希表+滑动窗口

• 用双指针定义一个滑动窗口，右指针指向的字符不在窗口中重复时，右指针进一步
• 当遇到重复字符时候，左指针收缩到字符上次出现的位置
• 用hashtable记录每一个字符出现的最新位置
• 记录窗口的最大长度

代码：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        length = 0
        hasmap = dict()
        left, right = 0, 0
        #1个字符返回
        if len(s) < 1:
            return len(s)
        hasmap[s[left]] = 0
        while right < len(s):
            #判断右指针指向的字符是否在当前滑动窗口中有重复
            if s[right] in s[left:right]:#说明重复
                length = max(length, right-left)
                left = hasmap[s[right]] + 1 #找到字符以前出现的位置，向前走一步
            else:
                length = max(length, right-left) #更新维护的不重复最大字串
            hasmap[s[right]] = right
            right = right + 1
        length = max(length, right - left)
        return length

复杂度分析：

• 时间复杂度：O(N)，N为字符串长度
• 空间复杂度： O(S), hashtable 维护的字符串中的元素个数，记录其位置

[dahaiyidi]

Problem

3. 无重复字符的最长子串

++

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

---

Note

• 移动窗口，重要的是熟悉语法运用。
• python: set的用法：add, remove
• C++: unordered_set: insert, erase, find
• 滑动窗口题目：
  • 30. 串联所有单词的子串
  • 76. 最小覆盖子串
  • 159. 至多包含两个不同字符的最长子串
  • 209. 长度最小的子数组
  • 239. 滑动窗口最大值
  • 567. 字符串的排列
  • 632. 最小区间
  • 727. 最小窗口子序列

---

Complexity

• 时间O：n
• 空间O：n

---

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res = 0
        lookup = set()
        length = 0
        left = 0

        for i in range(len(s)):
            length += 1
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                length -= 1
            lookup.add(s[i])
            if length > res:
                res = length

        return res

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> lookup;
        int res = 0;
        int length = 0;
        int left = 0;

        for(int i = 0; i < s.size(); i++){
            length++;
            while(lookup.find(s[i]) != lookup.end()){
                lookup.erase(s[left]);
                length--;
                left++;
            }
            lookup.insert(s[i]);
            res = max(length, res);
        }
        return res;
    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

[1916603886]

var lengthOfLongestSubstring = function(s) { const length = s.length; if(length === 0) return 0; if(length === 1) return 1; const set = new Set([s[0]]); let left = 0; let right = 0; let max = 0;

while(right<length-1) {
    if(set.has(s[right+1])) {
        set.delete(s[left++])
    }else{
        set.add(s[++right]);
        max = Math.max(max,set.size)
    }
}
return max;

};

[ForLittleBeauty]

思路

---

two pointer

---

代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        wordSet = set()
        left = right = 0
        maxLength = 0
        while right<len(s):
            if s[right] not in wordSet:
                wordSet.add(s[right])
                right += 1
            else:
                maxLength = max(right-left,maxLength)
                while s[right] in wordSet:
                    wordSet.remove(s[left])
                    left += 1
                wordSet.add(s[right])
                right += 1
        return max(maxLength,right-left)

---

时间复杂度: O(n)

空间复杂度: O(n)

[yinhaoti]

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if s == "":
            return 0
        if len(s) == 1:
            return 1

        re = -1
        for i in range(len(s)):
            hash_tb = {}
            sub_max = 0
            for j in range(i, len(s)):
                if s[j] not in hash_tb:
                    hash_tb[s[j]] = 1
                    sub_max += 1
                    if j == len(s) - 1:
                        re = max(re, sub_max)
                else:
                    re = max(re, sub_max)
                    break

        return re

[superduduguan]

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if (not s or len(s) == 0): return 0

    # stores last seen index of a character
    seen = {}
    res = left = 0

    for right, char in enumerate(s):
        if char in seen and left <= seen[char]:
            left = seen[char] + 1
        else:
            res = max(res, right - left + 1)
        seen[char] = right

    return res