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

[xil324]

var lengthOfLongestSubstring = function(s) {
    let maxLen = 0; 
    let left = 0, right = 0;
    const freqMap = {};
    while (right < s.length) {
        const char = s[right];
        if(char in freqMap) {
            freqMap[char] += 1;
        } else {
            freqMap[char] = 1;
        }
        while(freqMap[char] > 1) {
            freqMap[s[left]]--;
            left++; 
        }
        maxLen = Math.max(maxLen, right-left+1); 
        right++
    }
    return maxLen;
};

// time complexity: O(n) // space complexity: O(1)

[zhiyuanpeng]

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

Time O(N) Space O(N)

[Martina001]

思路：滑动窗口简单题 时间复杂度：O(n) 空间复杂度：O(n)

public int lengthOfLongestSubstring(String s) {
        // 滑动窗口
        HashMap<Character,Integer> window = new HashMap<>();
        int len = 0,l = 0,r = 0;
        while(r<s.length()){
            char c = s.charAt(r);
            r++;
            window.put(c,window.getOrDefault(c,0)+1);
            while(window.get(c)>1){
                char left = s.charAt(l);
                l++;
                window.put(left,window.getOrDefault(left,0)-1);
            }
            // 这一段要放在外面 以保证最后的无重复子串也能参与
            if(r-l >len){
                len = r-l;
            }
        }
        return len;
}

[rao-qianlin]

思路

使用滑动窗口

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int minLength = Integer.MIN_VALUE;
        char[] sc = s.toCharArray();

        int left = 0;
        int right = 0;

        HashMap<Character,Integer> window = new HashMap<>();

        while(right < sc.length){
            char c = sc[right];
            right ++;
            window.put(c, window.getOrDefault(c, 0) + 1);
            while(window.get(c)>1){
                char l = sc[left];
                left ++;
                window.put(l, window.get(l) - 1);
            }
            minLength = Math.max(minLength, right - left);

        }
        if(minLength == Integer.MIN_VALUE){
            return 0;
        }
        else{
            return minLength;
        }
    }
}

[atom-set]

思路

• 使用双指针
• 将双指针之间的字符串存放到哈希表里，判断右指针是否出现过
  • 出现，返回，重置左右指针和哈希表
  • 不出现，移动右指针，将元素放到哈希表里

代码

var lengthOfLongestSubstring = function (s) {
  if (!s) {
    return 0;
  }
  var leftPoint = 0;
  var rightPoint = 0;
  var len = s.length;
  var map = new Map();
  var max = 0;

  while (rightPoint < len) {
    var ch = s.charAt(rightPoint);
    if (!map.has(ch)) {
      map.set(ch, 1);
      rightPoint++;
      if (rightPoint === len) {
        max = max < map.size ? map.size : max;
        break;
      }
    } else {
      max = max < map.size ? map.size : max;
      leftPoint = leftPoint + 1;
      rightPoint = leftPoint;
      map.clear();
    }
  }

  return max;
};

复杂度分析

N 数据规模，M: 最长子串长度

• 时间复杂度: O(N)
• 空间复杂度: O(M)

[Yukibei]

用双指针（滑动窗口）

class Solution { public: int lengthOfLongestSubstring(string s) { int len = s.size(); int res = 0; int r = 0; unordered_set st; for (int i = 0; i < len; i ++) { while (r < len && !st.count(s[r])) { st.insert(s[r]); r ++; } res = max(res, r - i); st.erase(s[i]); } return res; } }; 时间空间为（n）

[Lizhao-Liu]

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        if s.isEmpty {
            return 0
        }
        var left = s.startIndex, right = s.startIndex
        var maxLength = Int.min
        var map = Set<Character>.init()
        while right < s.endIndex {
            if !map.contains(s[right]) {
                map.insert(s[right])
                right = s.index(after: right)
                maxLength = max(maxLength, s.distance(from: left, to: right))
            } else {
                map.remove(s[left])
                left = s.index(after: left)
            }
        }
        return maxLength
    }

}

[lxy1108]

思路

滑动窗口思想，当目前的子序列中包括重复字符的时候收紧子序列直到没有重复字符，遍历过程中计算最长无重复子序列的长度。 维护一个集合来记录当前子序列中的字符。

python3 代码

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

复杂度

时间复杂度o(n) 需要遍历一次字符串

空间复杂度o(k) k为字符集合占用的最大空间，即可能出现的字符个数

[Dtjk]

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> occ;
        int n = s.size();
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                occ.erase(s[i - 1]);
            }
            while (rk + 1 < n && !occ.count(s[rk + 1])) {
                occ.insert(s[rk + 1]);
                ++rk;
            }
            ans = max(ans, rk - i + 1);
        }
        return ans;
    }
};

[CathyShang]

思路 C++

update 2024-04-29

• 遍历 while(){... fast++;} 注意：边界位fast<n+1;
• 构建 hashmap，记录char最近一次索引;
• 快慢指针 slow, fast
  • 当fast指向重复char, 并且slow小于该char最近一次hashmap[char], 更新slow = hashmap[s[fast]]+1;
  • temp = fast-slow 目前不重复字符串长度，比较更新最长max_l;

    代码

    // update 2024-04-29
    class Solution {
    public:
    int lengthOfLongestSubstring(string s) {
    int slow = 0, fast = 0; // 快慢指针
    unordered_map<char, int> hash; // 哈希表
    int max_l=0; // 输出
    // string max_s = "";
    int n = s.size();
    if(n==1) return n;
    // note1: 字符串默认有一个"\0"长度位n，不到n，则"abc"仅输出"ab"
    while(fast<n+1){
        // cout << slow  <<":"<< fast<<  ":" << max_s;
        auto it = hash.find(s[fast]);
        int temp= fast-slow;
        if(it!=hash.end()){
            // note2: slow最远优先，而不是仅仅让slow=上一次重复的位置 不然 "abba"输出 "bba"
            if(slow < hash[s[fast]]+1){
                slow = hash[s[fast]]+1;
            }
        }
        hash[s[fast]]=fast;
        if(temp>max_l){
        max_l = temp;
        // max_s = s.substr(slow, temp); // 字符串截取 (start_idx, length)
        }
        fast++;
        // cout << endl;
    }
    return max_l;
    }
    };

    复杂度

• 时间 $O(N)$ 遍历字符串
• 空间 $O(1)$

[GReyQT]

题解思路：

（1）创建哈希表储字符和其出现次数的映射，其中键为字符，值为该字符在当前滑动窗口中出现的次数。 （2）使用两个值i和j来构建滑动窗口，其中i指向当前滑动窗口的起始位置，j用于遍历整个字符串。

代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> map;
        int len = s.length();
        int res = 0; // 最长字串长度
        int i = 0;   // 滑动窗口起始位置
        for (int j = 0; j < len; j++) 
        {
            map[s[j]]++;
            while (map[s[j]] > 1) 
            {
                map[s[i++]]--;
            }
            res = res > j - i + 1 ? res : j - i + 1;
        }
        return res;
    }
};

复杂度分析：

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

[smallppgirl]

滑动窗口

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> 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

时间O(n) 空间O(k)

[hillsonziqiu]

思路

双指针，从开始向后遍历内部指针向后遍历，然后内容用Set存储，这样可以以O（1）的复杂度快速获取值进行比较。

代码

/*
 * @lc app=leetcode.cn id=3 lang=javascript
 *
 * [3] 无重复字符的最长子串
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  const ss = new Set();
  let result = 0;
  let p = -1;
  for (let i = 0; i < s.length; i++) {
    if (i !== 0) {
      ss.delete(s.charAt([i - 1]));
    }

    while (p + 1 < s.length && !ss.has(s.charAt(p + 1))) {
      ss.add(s.charAt(p + 1));
      p++;
    }

    result = Math.max(result, p - i + 1);
  }

  return result;
};

复杂度分析

时间复杂度：O(n); 空间复杂度：O(m); m是所有不同字符集的长度