【Day 22 】2024-09-05 - 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" 是一个子序列，不是子串。

[akxuan]

首次提交AC slicing window， 找出set 的最大值。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # slicing window 
        used_char = set()
        res = 0 
        fast, slow = 0, 0 
        while fast < len(s):

            if s[fast] not in used_char:
                used_char.add(s[fast])
                res = max(res,len(used_char))
            else: 
                while s[slow] != s[fast]: 
                    used_char.remove(s[slow]) 
                    slow += 1
                slow += 1
            fast += 1
        return res

时间复杂度 O（N） 空间 O（1）， 因为set 最多24个字母

[godkun]

思路

• 暴力循环或者滑动窗口都能解决这个题目

代码

TS实现

function lengthOfLongestSubstring(s: string): number {
    let maxLength = 0;
    let start = 0;
    let map = new Map();
    for (let end = 0; end < s.length; end++) {
        const c = s[end];
        if (map.has(c) && map.get(c) >= start) {
            start = map.get(c) + 1;
        }

        map.set(c, end);
        maxLength = Math.max(maxLength, end - start + 1);
    }
    return maxLength;
}

复杂度分析

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

[huizsh]

class Solution:
# 暴力法
# 时间复杂度 O(n**2)
# 空间复杂度 O(n)
#    def lengthOfLongestSubstring(self, s: str) -> int:
#        ans = 0
#        n = len(s)
#        for i in range(n):
#            m = collections.defaultdict(int)
#            for j in range(i, n):
#                if m[s[j]] != 0:
#                    break
#                m[s[j]] = 1
#                ans = max(ans, j - i + 1)
#        return ans

# 滑动窗口，l和r指针维护一个移动窗口，移动窗口里字符不重复，遍历一遍字符串，发现重复字符，把左指针指向字符上一次出现时的下个位置
# 用一个字典记录字符最新出现的位置
# 时间复杂度 O（n)
# 空间复杂度 O (m) m为字符集元素个数
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0
        n = len(s)
        m = {}
        l = r = 0
        while r < n:
            pos = m.get(s[r], -1)
            if (pos >=l and pos <= r): l = pos + 1
            m[s[r]] = r
            ans = max(ans, r - l + 1)
            r = r + 1
        return ans

[CelesteXiong]

Intuition

Slide windows by two pointers

Algorithm

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        location = {}
        left = 0
        right = 0
        result = 0
        while left <= right and right <= len(s) - 1:
            if s[right] not in location:
                location[s[right]] = right
            else:
                left = max(left, location[s[right]]+1)
                location[s[right]] = right
            result = max(result, right-left+1)
            right += 1
        return result

Complexity

Time: O(n), where n is the length of the string s

Space: O(n)

[sleepydog25]

Approach

sliding window technique

Algorithm

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set <Character> storage = new HashSet <>();

        int start = 0;
        int answer = 0;

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

            Character current = s.charAt(i);

            while (storage.contains(current)){
                char remove = s.charAt(start);
                storage.remove(remove);
                start ++;
            }
            storage.add(current);

            answer = Math.max(i-start+1 , answer);
        }    
        return answer;    
    }
}

Complexity

1. Time Complexity:O(n)
2. Space Complexity:O(n)

[zjy-debug]

代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set()  # 用来存储当前窗口的字符
        left = 0  # 窗口的左边界
        max_length = 0  # 最长子串的长度

        for right in range(len(s)):  # 右边界遍历字符串
            while s[right] in char_set:  # 如果右边界字符在集合中，说明有重复
                char_set.remove(s[left])  # 移动左边界，直到没有重复
                left += 1
            char_set.add(s[right])  # 添加右边界字符到集合中
            max_length = max(max_length, right - left + 1)  # 更新最长子串长度

        return max_length

[peggyhao]

class Solution {
    public int lengthOfLongestSubstring(String s) {

        Set<Character> occ = new HashSet<Character>();
        int n = s.length();

        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {

                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {

                occ.add(s.charAt(rk + 1));
                ++rk;
            }

            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

[Fightforcoding]

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        seen = defaultdict(int)
        maxlen = 0
        start = 0
        for end in range(len(s)):
            char = s[end]
            if char in seen and seen[char] >= start:
                start = seen[char]  + 1
            seen[char] = end
            maxlen = max (maxlen, end - start + 1)
        return maxlen

Time O(N) Space O(N)