【Day 22 】2021-10-01 - 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" 是一个子序列，不是子串。

[yanglr]

思路:

方法: 哈希表 + 滑动窗口

• 定义一个哈希表dict存放各个字符及其出现的位置；

• 定义两个指针 i, j 分别表示不重复子串的开始位置和结束位置；

• j 向后遍历，若遇到与 [i, j] 区间内字符相同的元素，更新 i 的值，此时 [i, j] 区间内不存在重复字符，计算 res 的最大值。

代码

实现语言: C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length(), res = 0;
        unordered_map<char, int> dict;
        // 双指针i, j
        for (int j = 0, i = 0; j < n; j++)
        {
            if (dict.find(s[j]) != dict.end()) // 如果当前字符出现过，curStartIdx (即这里的 i)更新为该字符上一次出现的位置
            {
                i = max(dict[s[j]], i); 
            }
            res = max(res, j - i + 1);  // 使用贪心思想进行子串延伸，关键!
            dict[s[j]] = j + 1;         /* 如果当前字符没出现过，将其index记录在dict中。下标 +1 代表 i 要移动的下个位置。 */
        }
        return res;        
    }
};

复杂度分析

• 时间复杂度：O(N)，N 为 s 长度。
• 空间复杂度：O(d)，d 是字符集的大小，最大会达到哈希表的大小N，故最大为 O(N)。

[BpointA]

思路

哈希表+滑动窗口。思路1是记录字母最后一次出现的位置，便于指针移动。思路2记录字母出现次数，依次移动指针，直至达到要求。

思路1 Python代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        from collections import defaultdict
        res=0
        d=defaultdict(int)
        left=0
        right=0
        while right<len(s):
            lt=s[right]
            right+=1
            if lt in d:
                left=max(left,d[lt]+1)
            d[lt]=right-1
            res=max(res,right-left)
        return res          

思路2 Python代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        from collections import defaultdict
        res=0
        d=defaultdict(int)
        left=0
        right=0
        while right<len(s):
            lt=s[right]
            right+=1
            d[lt]+=1
            while d[lt]==2:
                d[s[left]]-=1
                left+=1
            res=max(res,right-left)
        return res

复杂度

时间复杂度：O(n)，左右指针分别遍历数组

空间复杂度：O(s)，以字母为键构建哈希表

[KennethAlgol]

思路

滑动窗口

语言

java

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;
    }
}

复杂度分析

空间复杂度 O(n)

[leungogogo]

LC3. Longest Substring Without Repeating Characters

Method 1. Sliding Window + HashSet

Main Idea

Two pointers, if no repeat, increment fast, else, keep incrementing slow until we remove the duplicate, so in the worst case we need to traverse each element exactly twice.

Code

• CPP

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        unordered_set<char> set;
        int l = 0, r = 0, res = 0;
        while (r < n) {
            while(r < n && set.find(s[r]) == set.end()) {
                set.insert(s[r++]);
            }

            res = max(res, r - l);
            while(set.find(s[r]) != set.end()) {
                set.erase(s[l++]);
            }
        }
        return res;
    }
};

Complexity Analysis

Time: O(2n) = O(n) Space: O(n)

Method 2. One Scan with Map

Main Idea

In Method 1, we need to move the left boundary of the sliding window step by step, which causes extra runtime. Actually, we can use a map to record the index of last occurrences of each character, and when seeing repeated character, we can get its previous index, and left = index + 1.

Code

• CPP

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        unordered_map<char, int> map;
        int l = 0, r = 0, res = 0;
        while (r < n) {
            while (r < n && (map.find(s[r]) == map.end() || map[s[r]] < l)) {
                map[s[r++]] = r;
            }
            res = max(res, r - l);
            if (r >= n) break;
            l = map[s[r]] + 1;
        }
        return res;
    }
};

Complexity Analysis

Time: O(n)

Space: O(n)

[pophy]

思路

• 双指针滑动窗口
• 利用set记录窗口内的元素
• 右指针发现重复元素 A 后
  • 更新count
  • 左指针移动至 第一个 A 处
  • 左右指针++

Java code

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int low = 0, high = 0, count = 0;
        Set<Character> window = new HashSet();
        while (high < s.length()) {            
            while (high < s.length() && !window.contains(s.charAt(high))) {
                window.add(s.charAt(high));
                high++;
            }
            count = Math.max(count, high - low);
            //expand high, move low
            while (high < s.length() && s.charAt(low) != s.charAt(high)) {
                window.remove(s.charAt(low));
                low++;
            }
            low++;
            high++;
        }
        return count;
    }

时间&空间

• 时间 O(n）
• 空间 O(n)

[thinkfurther]

思路

用双指针做滑动窗口，用set存放字符

代码

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

        first = 0
        second = 1
        current_string = set()
        current_string.add(s[0])
        longest = 1

        while second != len(s):
            while (s[second] in current_string):
                current_string.remove(s[first])
                first += 1
            current_string.add(s[second])
            longest = max(longest, len(current_string))
            second += 1

        return longest

复杂度

时间复杂度 ：O(N)

空间复杂度：O(s)

[erik7777777]

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int res = 0;
        int i = 0;
        int j = 0;
        while (j < s.length()) {
            char c = s.charAt(j++);
            while (i < s.length() && set.contains(c)) {
                set.remove(s.charAt(i++));
            }
            set.add(c);
            res = Math.max(res, set.size());
        }
        return res;
    }
}

复杂度 time : O(n) space : O(n)

[falconruo]

思路:

滑动窗口(双指针)法:

• 用一个指针l记录窗口的左边界, 另一个指针i记录窗口右边界，整个窗口用hashmap记录
• 出现重复字符s[i], 在hashmap里查找重复字符s[i]出现的位置index = dict[s[i]],收缩窗口左边界,将 0 - index之间的字符移出窗口, 在边界从index + 1开始 (l = index + 1)
• 继续滑动右边界i,直至结束

复杂度分析:

时间复杂度: O(n), n为字符串长度 空间复杂度: O(n)

代码(C++):

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();

        if (n <= 1) return n;

        unordered_map<char, int> dict;

        int maxlen = 0;
        int l = 0;
        for (int i = 0; i < n; ++i) {
            if (dict.count(s[i]) && l <= dict[s[i]])
                l = dict[s[i]] + 1;

            dict[s[i]] = i;
            maxlen = max(maxlen, i - l + 1);
        }

        return maxlen;
    }
};

[Daniel-Zheng]

思路

HashSet。

代码(C++)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> hashSet;
        int left = 0;
        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            if (hashSet.count(s[i])) {
                int len = hashSet.size();
                res = max(res, len);
                while (s[left] != s[i]) {
                    hashSet.erase(s[left]);
                    left++;
                }
                left += 1;
            } else {
                hashSet.insert(s[i]);
            }
        }
        int len = hashSet.size();
        return max(res, len);
    }
};

复杂度分析

• 时间复杂度：O(N)，N为S长度。
• 空间复杂度：O(S)，S为HashSet里元素个数。

[zhangzz2015]

思路

• 对于处理重复考虑使用hash_map记录是否字符出现过，对于字串问题考虑是否可使用sliding windows。这个问题是比较典型的sliding window应用。另外由于字符只有256，可使用vector替代hashmap，用来记录字符出现的次数，当hashmap中的字符出现的次数没有超过1次，就移动right。当有超过1次的情况，则表明[left right]子串中有重复字符，则移动left。收集最大的窗口大小，就是最长没有重复的子串。时间复杂度为O(N)，空间复杂度为O(256)，也就是O(1)。

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        ///  use siding window. 
        int left =0; 
        int right =0; 
        vector<int> record(256,0); 
        int ret =0; 
        while(right<s.size())
        {

             record[s[right]]++;  

            while(record[s[right]]>1)
            {
                record[s[left]]--; 
                left++; 
            }

            ret = max(ret, right-left+1);                         
            right++; 
        }

        return ret; 
    }
};

[zhy3213]

思路

哈希+双指针

代码

    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s)==0:
            return 0
        fast,slow=0,0
        res=1
        l=1
        char={s[0]:0}
        while fast<len(s)-1:
            fast+=1
            l+=1
            if s[fast] in char:
                ind=char[s[fast]]
                l-=ind-slow+1
                for i in s[slow:ind+1]:
                    del char[i]
                slow=ind+1
                char[s[fast]]=fast
            else:
                char[s[fast]]=fast
                if l>res:
                    res=l
        return res

时间复杂度O(N) 空间复杂度O(1)

[ginnydyy]

Problem

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

Notes

• Sliding window + hash map (sliding window + hash set can also solve the problem, just need to compare the left pointer to the duplicate character while moving the left pointer).
• Use hash map to record the visited characters and the corresponding indexes, while sliding the right pointer.
• When visiting a duplicate character
  • update the max length
  • get the last visited index from the map, and move the left pointer to the index + 1 position
  • remove the visited characters from the map while sliding the left pointer
  • add the current character to the map
• After the right pointer moves out of the string length range, remember to update the max length for the last time before returning it. i.e. "au".

Solution

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() < 2){
           return s.length(); 
        }
        Map<Character, Integer> map = new HashMap<>();
        int left = 0;
        int right = 0;
        int max = 0;
        while(right < s.length()){
            if(map.containsKey(s.charAt(right))){
                max = Math.max(max, right - left);
                int index = map.get(s.charAt(right));
                while(left <= index){
                    map.remove(s.charAt(left));
                    left++;
                }
            }
            map.put(s.charAt(right), right);
            right++;
        }

        max = Math.max(max, right - left); // right is out of s length range

        return max;
    }
}

Complexity

• Time: O(n) n is the length of the string.
• Space: O(n).

[yingliucreates]

link:

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

代码 Javascript

const lengthOfLongestSubstring = function (s) {
  // keeps track of the most recent index of each letter.
  const seen = new Map();
  // keeps track of the starting index of the current substring.
  let start = 0;
  // keeps track of the maximum substring length.
  let maxLen = 0;

  for (let i = 0; i < s.length; i++) {
    // if the current char was seen, move the start to (1 + the last index of this char)
    // max prevents moving backward, 'start' can only move forward
    if (seen.has(s[i])) start = Math.max(seen.get(s[i]) + 1, start);
    seen.set(s[i], i);
    // maximum of the current substring length and maxLen
    maxLen = Math.max(i - start + 1, maxLen);
  }

  return maxLen;
};

复杂度分析

time & space : O(n)

[heyqz]

代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l, res = 0, 0
        dic = {}
        for i, c in enumerate(s):
            if c in dic and l <= dic[c]:
                l = dic[c] + 1
            else:
                res = max(res, i - l + 1)

            dic[c] = i

        return res

复杂度

time complexity: O(N) space complexity: O(N)

[zol013]

思路： 设置left, right 滑动窗口的两端 初始为0. right开始向右滑行并用记录见过的字母，当right读到重复字母的时候，开始删除hashset里左端的字母，并把left + 1 Python 3 Code:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:       
        l = r = 0
        ans = 0
        seen = set()
        while r < len(s):
            while seen and s[r] in seen:
                seen.remove(s[l])
                l += 1
            ans = max(ans, r  - l + 1)
            seen.add(s[r])
            r += 1
        return ans

Time Complexity: O(N) Space Complexity: O(N)

[nonevsnull]

思路

• 拿到题的直觉解法
  • 用两个指针，left,right，从起点出发；
  • 如果没有遇到重复的，right++，将值和index存入map
  • 如果遇到了重复的，且重复的在左指针右边，将左指针挪到右指针所在位置，更新map
  • 循环的每一步都更新长度max

AC

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();

        int left = 0, max = Integer.MIN_VALUE;

        for(int right = 0;right < s.length();right++){
            char c = s.charAt(right);
            if(map.containsKey(c) && map.get(c) >= left){
                left = map.get(c) + 1;
                map.put(c, right);
            } else {
                map.put(c, right);
            }
            max = Math.max(max, right - left + 1);
        }
        return max == Integer.MIN_VALUE?0:max;
    }
}

复杂度

time: O(N); space：map所需的空间O(N)

[cicihou]

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cache = {}
        start = res = 0
        for i, ch in enumerate(s):
            if ch in cache and cache[ch] >= start:
                start = cache[ch] + 1
            else:
                res = max(res, i - start + 1)
            cache[ch] = i
        return res

[st2yang]

思路

• 双指针，滑动窗口

代码

• python

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

复杂度

• 时间: O(n)
• 空间: O(min(m, n))

[wangzehan123]

class Solution {
  public int lengthOfLongestSubstring(String s) {
        char[] cs = s.toCharArray();
        // start：为重复元素的下一个元素的下标 + 1
        int max = 0, start = 0;
        // key:字符   value:字符的下标
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < cs.length; i++) {
            if(map.containsKey(cs[i]) && map.get(cs[i]) >= start){
                Integer preIndex = map.get(cs[i]);
                max = Math.max(max, i - start);
                start = preIndex + 1;
            }
            map.put(cs[i], i);
        }
        // 最后一次如果没有遇到重复的字符，需要计算
        max = Math.max(max, cs.length - start);
        return max;
  }
}

复杂度分析

令 n 为数组长度。

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

[james20141606]

Day 22: 3. Longest Substring Without Repeating Characters (hashtable, sliding window, two pointers)

• Problem Link

  • 3. Longest Substring Without Repeating Characters

• Ideas

  • Very classic sliding window problem. Note that we only need to record and return the max_length value. But The start point of the maximum length substring could change depend on if a letter has been seen before. If seen and the start point is <= the letter last seen, then we should update the start point (for example "tmmzuxt", the first t is outdated, do not need to reset start). For novice like me, one tricky part which requires more thinking is that some cases like aa means the previous maximum substring is ruined, but it doesn't matter since it is recorded in max_length and used

• Complexity: hash table and bucket

  • Time: O(N)
  • Space: O(s) worst case N

• Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start = 0
        max_length = 0
        used = {}
        for count, string in enumerate(s):
            if string in used and start <= used[string]: 
                start = used[string] + 1
            else:
                max_length = max(max_length, count - start+1)
            used[string] =  count
            print (used, start, used[string])
        return max_length

• other resources:

[akxuan]

class Solution(object): def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ used = {} max_length = start = 0 for i, c in enumerate(s): if c in used and start <= used[c]: start = used[c] + 1 else: max_length = max(max_length, i - start + 1)

        used[c] = i

    return max_length

[yachtcoder]

Two pointers. O(n) and O(n).

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ret, l = 0, 0
        counter = Counter()
        for r in range(len(s)):
            c = s[r]
            counter[c] += 1
            while counter[c] > 1:
                counter[s[l]] -= 1
                l += 1
            ret = max(ret, r-l+1)
        return ret

[MonkofEast]

3. Longest Substring Without Repeating Characters

Click Me

Algo

1. sliding window + hashmap
2. "slow" should never turn back
3. careful about the sequence of updating res - updating fast - updating hashmap -

Code

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        # corner
        if len(s) <= 1: return len(s)

        fast = slow = 0
        hashmap = {}

        res = 1

        while fast < len(s):
            if s[fast] in hashmap:
                if slow < hashmap[s[fast]] + 1: slow = hashmap[s[fast]] + 1
            hashmap[s[fast]] = fast
            res = max(res, fast - slow + 1)            
            fast += 1

        return res

Comp

T: O(N)

S: O(len(unique(s)))

[kidexp]

thoughts

窗口指针 加 hashmap 存每个char的个数

每次要check 当前char的个数>1 往后挪

code

class Solution:    
    def lengthOfLongestSubstring(self, s: str) -> int:
        """
        sliding window template
        """
        from collections import defaultdict
        if len(s) <= 1:
            return len(s)
        start = 0
        char_count_map = defaultdict(int)
        max_length = 0
        for i, char in enumerate(s):
            char_count_map[char] += 1
            while char_count_map[char] > 1:
                char_count_map[s[start]] -= 1
                start += 1
            max_length = max(max_length, i - start+1)
        return max_length

complexity

time O(n)

space O(n) 可以优化到O(1）如果都是asic 码

[mmboxmm]

思路

模版题，虽然稍微有点特殊

代码

fun lengthOfLongestSubstring(s: String): Int {
  val map = IntArray(128) { -1 }
  var max = 0
  var start = 0

  for (end in s.indices) {
    val last = map[s[end].code]
    if (last != -1) {
      max = maxOf(max, end - start)
      (start..last).forEach { map[s[it].code] = -1 }
      start = last + 1
    }
    map[s[end].code] = end
  }

  return maxOf(max, s.length - start)
}

复杂度分析

O(n)

[Laurence-try]

思路

滑动窗口和哈希表结合。利用一个指针记录上一次窗口（不重复字母）的开始的位置，如有重复，此时此指针移动到上一个此重复字母的+1 的位置。每次查是否有重复字母检查此字母到这个指针的长度，如比max_length大则跟新。

代码

使用语言：Python3

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        p = 0
        max_length = 0
        win = {}
        for index, ch in enumerate(s):
            if ch in win and p <= win[ch]:
                p = win[ch] + 1
            else:
                max_length = max(max_length, index - p + 1)
            win[ch] = index   
        return max_length

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

[ivalkshfoeif]

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] set = new int[128];
        int l = 0, r = 0;
        int maxL = 0;
        while (r < s.length()){
            char rc = s.charAt(r);
            set[rc]++;
            while (set[rc] > 1){
                char lc = s.charAt(l);
                set[lc]--;
                l++;
            }

            maxL = Math.max(r - l + 1, maxL);

            r++;

        }
        return maxL;
    }
}

用map的写法，感觉容易写错

[BlueRui]

Problem 3. Longest Substring Without Repeating Characters

Algorithm

• Use two pointers to represent a sliding window, and use a set to keep characters in the window. The max window size is the length of the longest substring.
• First set both points i and j at that beginning of the string. Move j to the right if the current character is not already in the set.
• If j points to a character c that is already in the set, remove character at i from the set and move i to the right until c is no longer in the set.
• Continue to move j till the end of the string.

Complexity

• Time Complexity: O(N) as we traverse the string once.
• Space Complexity: O(N) which is the max size of the set.

Code

Language: Java

public int lengthOfLongestSubstring(String s) {
    int max = 0;
    Set<Character> set = new HashSet<>();
    int i = 0;
    for (int j = 0; j < s.length(); j++) {
        Character c = s.charAt(j);
        while (set.contains(c)) {
            set.remove(s.charAt(i++));
        }
        set.add(c);
        max = Math.max(max, set.size());
    }
    return max;
}

[xj-yan]

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();

        int leftBound = 0, maxLen = 0;
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                leftBound = Math.max(leftBound, map.get(c) + 1);
            }
            map.put(c, i);
            maxLen = Math.max(maxLen, i - leftBound + 1);
        }
        return maxLen;
    }
}

Time Complexity: O(n), Space Complexity: O(n)

[ningli12]

思路

1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）, 此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值； 2、如果当前字符 ch 包含在 map中，此时有2类情况：

• 当前字符包含在当前有效的子段中，
• 当前字符不包含在当前最长有效子段中 为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1). 另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i， 因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int countMax = 0; 
        int left = 0;

        HashMap<Character, Integer> map = new HashMap<>();
        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); 
            countMax = Math.max(countMax, i - left + 1);
        }

        return countMax; 
    }
}

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

[laofuWF]

# sliding window
# maintain a window of substring without duplicate
# store index of last seen char in a dict with key: char, value: index
# when encounter repeating char, remove all char from left pointer to last seen index of the char

# time: O(N)
# space: O(N)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        res = float('-inf')
        window = {}
        left = 0
        for right, char in enumerate(s):
            # repeating character found
            if window.get(char, -1) != -1:
                prev_index = window.get(char)
                while left <= prev_index:
                    # remove elements in between
                    window[s[left]] = -1
                    left += 1
            res = max(res, right - left + 1)
            window[char] = right

        return res

[florenzliu]

Explanation

• use sliding window, within which there is no repetitive numbers
• use a hashset to store all the traversed numbers in the sliding window
• use maxLength to store the current max length

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0 
        maxLen = 0
        h = set()
        for i in range(len(s)):
            if s[i] not in h:
                h.add(s[i])
                maxLen = max(maxLen, i-left+1)
            else:
                while s[i] in h:
                    h.remove(s[left])
                    left += 1
                h.add(s[i])
        return maxLen  

Complexity:

• Time Complexity: O(N)
• Space Complexity: O(N)

[bingyingchu]

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

        left = 0
        window = []
        count = 0

        for right in range(len(s)):
            while s[right] in window:
                window.pop(0)
                left += 1
            window.append(s[right])
            count = max(right - left + 1, count)

        return count

Time/Space: O(n)

[xieyj17]

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

        i, j = 0, 1
        max_len = 0
        while j <= len(s):
            if len(set(s[i:j])) == (j-i):
                max_len = max(max_len, j-i)
                j += 1
            else:
                i += 1
        return max_len

使用双指针，hash table 的答案看了官方解答之后明白了

Time: O(N^2)

Space: O(N)

[Menglin-l]

思路：

滑窗

---

代码部分：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        if (length <= 1) return length;

        int maxLen = 0;
        int l = 0, r = 0;
        HashMap<Character, Integer> res = new HashMap<>();

        while (r < length) {
            char right = s.charAt(r);
            int rightIndex = res.getOrDefault(right, -1);
            l = Math.max(l, rightIndex + 1);

            maxLen = Math.max(maxLen, r - l + 1);
            res.put(right, r);
            r ++;
        }

        return maxLen;
    }
}

---

复杂度：

Time: O(N)

Space: O(N)

[carsonlin9996]

hashmap 存 index， 当遇到已存在的字母移动left指针

class Solution {
    public int lengthOfLongestSubstring(String s) {

        Map<Character, Integer> indexMap = new HashMap<>();

        int left = 0;

        int max = 0;

        for (int i = 0; i < s.length(); i++) {

            if (!indexMap.containsKey(s.charAt(i))) {
                indexMap.put(s.charAt(i), i);
                max = Math.max(max, i - left + 1);
            } else {
                left = Math.max(left, indexMap.get(s.charAt(i)) + 1);
                indexMap.put(s.charAt(i), i);
                max = Math.max(max, i - left + 1);

            }
        }

        return max;

    }
}

[tongxw]

思路

滑动窗口，用集合来判断窗口中是否有重复字符。 右指针前进时，如果指向的字符在窗口中，则左指针前进，把指向的字符从窗口中移除。直到窗口没有重复字符为止，或者左指针追上右指针。

代码

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const window = new Set();
    let l = 0;
    let ans = 0;
    for (let r = 0; r<s.length; r++) {
      while(window.has(s[r]) && l < r) {
        window.delete(s[l]);
        l++;
      }
      window.add(s[r]);
      ans = Math.max(ans, r - l + 1);
    }

    return ans;
};

复杂度分析

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

[Mahalasu]

思路

hashmap记录某个char的最右的位置，若出现重复，则将left改变到left或者char最右位置+1

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        count = {}
        ans = 0
        left = 0

        for right in range(len(s)):
            char = s[right]
            if char in count:
                left = max(left, count[char] + 1)
            count[char] = right
            ans = max(ans, right - left + 1)

        return ans

T: O(N) S: O(N)

[skinnyh]

Note

• Use a set and two pointers from the head. Iterate the end pointer, if the set already has the char at end, then keep removing from set and moving start to the right until no duplicate. Then update the result with the current substring length.
• Use a dict to record the last seen index of each char. Iterate each char in string as the end of a substring, if the current char has been seen before then update start as max(start, dict[s[end]] + 1). Update the result with each substring's length.

Solution1 - set

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start = end = res = 0
        sub = set()
        for end in range(len(s)):
            while s[end] in sub:
                sub.remove(s[start])
                start += 1
            sub.add(s[end])
            res = max(res, len(sub))
        return res

Time complexity: O(N)

Space complexity: O(N)

Solution2 - dict

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start = res = 0
        sub = {}
        for end in range(len(s)):
            if s[end] in sub:
                # case: abba, start need to be the max of prev start and last seen index
                start = max(start, sub[s[end]] + 1)
            sub[s[end]] = end
            res = max(res, end - start + 1)
        return res

Time complexity: O(N)

Space complexity: O(N)

[qyw-wqy]

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] count = new int[128];
        int res = 0;
        for (int l = 0, r = 0; r < s.length(); r++) {
            count[s.charAt(r)]++;
            while (count[s.charAt(r)] > 1) {
                count[s.charAt(l++)]--;
            }
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}

Time: O(n) Space: O(n)

[cassiechris]

思路

官方题解

代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        occ = set()
        n = len(s)
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                occ.add(s[rk + 1])
                rk += 1
            ans = max(ans, rk - i + 1)
        return ans

复杂度分析

• 时间复杂度: $O(N)$，N为为字符串长度
• 空间复杂度: $O(s)$，s为字符集元素个数

[carterrr]

class Solution { public int lengthOfLongestSubstring(String s) { int left = 0, maxLen = 0; // 滑动窗口定义常见左右指针方式 显式定义一个 另一个是循环下标 Map<Character,Integer> map = new HashMap<>(); for(int i = 0; i < s.length(); i ++){ Integer chooseableLeft = map.get(s.charAt(i)); if(chooseableLeft != null){ // 窗口只能缩减 左边界不能向左扩张 // left > chooseableLeft + 1 时chooseableLeft + 1 才能更新为新的更大的左边界 // 例如 ： // abca -> chooseableLeft = 0 -> left = 1 // abba -> i = 第二个b的时候 chooseableLeft = 1 ； i=第二个a的时候 chooseableLeft = 0 , left = 1这是不对的 被历史信息干扰了 因为之前的a的最终位置还没更新 left = Math.max(left, chooseableLeft + 1); } map.put(s.charAt(i), i); // 更新字符的位置 maxLen = Math.max(maxLen, i - left + 1); } return maxLen; } }

[chenming-cao]

解题思路

哈希表+滑动窗口。建立哈希表储存字符和字符前一次出现的下标。使用变量start记录最长无重复字符串的起始点，用max记录最长无重复字符串的长度。遍历字符串，如果遇到重复字符，将字符之前出现的位置和start比较，取较大的作为新的起始点，每次更新max。遍历结束返回max即为结果。

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int start = 0;
        int max = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                start = Math.max(map.get(c) + 1, start);               
            }
            map.put(c, i);
            max = Math.max(max, i - start + 1);
        }
        return max;
    }
}

复杂度分析

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

[comst007]

3. 无重复的最长字串

---

思路

滑动窗口 + 哈希表

代码

• C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();

        if(n < 2) return n;
        int ii, jj, ans;
        unordered_map<char,int> h_cnt;

        ans = 0;
        h_cnt[s[0]] ++ ;
        for(ii = 0, jj = 1; jj < n; ++ jj){
            h_cnt[s[jj]] ++ ;
            if(h_cnt[s[jj]] == 1){

                ans = max(jj - ii + 1, ans);

                continue;
            }
            while(s[ii] != s[jj]){
                h_cnt[s[ii]] --;
                ++ ii;
            }
            h_cnt[s[ii]] --;
            ++ ii;

            ans = max(ans, jj - ii + 1);

        }
        return ans;
    }
};

---

复杂度分析

n 为数组元素个数。

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

[RocJeMaintiendrai]

题目

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

思路

类似滑动窗口的思想，使用一块一慢双指针+ hashmap，j相当于头，i相当于尾巴，记录下character和对应的index，当遇到map中存的character时，移动j

代码

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

复杂度分析

时间复杂度

O(n)

空间复杂度

O(n)

[ChiaJune]

思路

hash + 滑动窗口

代码

var lengthOfLongestSubstring = function(s) {
  var set = new Set();
  var len = s.length;
  var count = 0;
  var r = 0, l = 0;
  for (; l < len; l++) {
    if (l > 0) {
      set.delete(s[l - 1]);
    }

    while (r < len && !set.has(s[r])) {
      set.add(s[r]);
      ++r;
    }

    count = Math.max(count, r - l);
  }
  return count;
};

复杂度

时间：O(n) 空间：O(n)

[hwpanda]

var lengthOfLongestSubstring = function(s) {
  const memo = new Map();
      let max = 0;
      let i = 0 ;
      let j = 0;
      while(i < s.length){
          if(memo.has(s[i])) {
              j = memo.get(s[i]) >= j ? memo.get(s[i]) + 1 : j;
              memo.set(s[i] , i);
              max = Math.max(max, i - j + 1);
              i++;
          }else{
              memo.set(s[i], i);
              max = Math.max(max, i - j + 1);
              i++;
          }
      }
      return max;
  };

[m-z-w]

var lengthOfLongestSubstring = function(s) {
    let set = new Set()
    let r = -1
    let maxLen = 0
    let n = s.length
    for (let i = 0; i < n; i++) {
        if (i !== 0) {
            set.delete(s.charAt(i - 1))
        }
        while (r + 1 < n && !set.has(s.charAt(r + 1))) {
            r++
            set.add(s.charAt(r))
        }
        maxLen = Math.max(maxLen, r - i + 1)
    }
    return maxLen
};

时间：O(n) 空间：O(n)

[xjlgod]

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, right = 0, res = 0, window = 0;
        while (right < len) {
            map.put(s.charAt(right), map.getOrDefault(s.charAt(right), 0) + 1);
            window += 1;
            while (map.get(s.charAt(right)) > 1) {
                map.put(s.charAt(left), map.get(s.charAt(left)) - 1);
                left++;
                window--;
            }
            res = Math.max(res, window);
            right++;
        }
        return res;
    }
}

[Moin-Jer]

思路

---

使用滑动窗口，并用set集合记录窗口中的元素

代码

---

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

复杂度分析

---

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