无重复字符的最长子串

Tips

题目类型: Sliding Window

题目

给定一个字符串, 找出其中不含有重复字符的最长子串的长度.

提示:

0 <= s.length <= 5 * 10⁴
s 由英文字母, 数字, 符号和空格组成

示例

输入: s = "bacabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc", 所以其长度为 3.

输入: s = "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke", 所以其长度为 3.

题解

Slide 1 of 10

JavaScript
Rust

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  const n = s.length
  const map = new Map()
  let start = 0
  let end = 0
  let max = 0

  while (end < n) {
    const endCh = s[end++]
    map.set(endCh, map.has(endCh) ? map.get(endCh) + 1 : 1)

    while (map.get(endCh) > 1) {
      const startCh = s[start++]
      map.set(startCh, map.get(startCh) - 1)
    }

    max = Math.max(max, end - start)
  }

  return max
}

use std::{cmp, collections::HashMap};

pub fn length_of_longest_substring(s: String) -> i32 {
    let s_bytes = s.as_bytes();
    let mut max = 0;
    let mut map: HashMap<u8, i32> = HashMap::with_capacity(26);
    let mut start = 0;
    let mut end = 0;

    while end < s.len() {
        let end_ch = s_bytes[end];
        end += 1;
        map.entry(end_ch).and_modify(|e| *e += 1).or_insert(1);

        while map[&end_ch] > 1 {
            let start_ch = s_bytes[start];
            start += 1;
            map.entry(start_ch).and_modify(|e| *e -= 1);
        }

        max = cmp::max(end - start, max);
    }

    max as i32
}

复杂度分析

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

题目​

题解​

复杂度分析​

题目

题解

复杂度分析