Question

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

English Version

题目描述

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

 

示例 1:

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

示例 2:

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

示例 3:

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

 

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

解法

方法一：双指针 + 哈希表

定义一个哈希表记录当前窗口内出现的字符，记 $i$ 和 $j$ 分别表示不重复子串的开始位置和结束位置，无重复字符子串的最大长度记为 ans。

遍历字符串 s 的每个字符 $s[j]$，我们记为 $c$。若 $s[i..j-1]$ 窗口内存在 $c$，则 $i$ 循环向右移动，更新哈希表，直至 $s[i..j-1]$ 窗口不存在 c，循环结束。将 c 加入哈希表中，此时 $s[i..j]$ 窗口内不含重复元素，更新 ans 的最大值。

最后返回 ans 即可。

时间复杂度 $O(n)$，其中 $n$ 表示字符串 s 的长度。

双指针算法模板：

for (int i = 0, j = 0; i < n; ++i) {
  while (j < i && check(j, i)) {
    ++j;
  }
  // 具体问题的逻辑
}

class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
    ss = set()
    ans = i = 0
    for j, c in enumerate(s):
      while c in ss:
        ss.remove(s[i])
        i += 1
      ss.add(c)
      ans = max(ans, j - i + 1)
    return ans

class Solution {
  public int lengthOfLongestSubstring(String s) {
    boolean[] ss = new boolean[128];
    int ans = 0;
    for (int i = 0, j = 0; j < s.length(); ++j) {
      char c = s.charAt(j);
      while (ss[c]) {
        ss[s.charAt(i++)] = false;
      }
      ss[c] = true;
      ans = Math.max(ans, j - i + 1);
    }
    return ans;
  }
}

class Solution {
public:
  int lengthOfLongestSubstring(string s) {
    bool ss[128]{};
    int ans = 0;
    for (int i = 0, j = 0; j < s.size(); ++j) {
      while (ss[s[j]]) {
        ss[s[i++]] = false;
      }
      ss[s[j]] = true;
      ans = max(ans, j - i + 1);
    }
    return ans;
  }
};

func lengthOfLongestSubstring(s string) (ans int) {
  ss := [128]bool{}
  for i, j := 0, 0; j < len(s); j++ {
    for ss[s[j]] {
      ss[s[i]] = false
      i++
    }
    ss[s[j]] = true
    ans = max(ans, j-i+1)
  }
  return
}

function lengthOfLongestSubstring(s: string): number {
  let ans = 0;
  const ss: Set<string> = new Set();
  for (let i = 0, j = 0; j < s.length; ++j) {
    while (ss.has(s[j])) {
      ss.delete(s[i++]);
    }
    ss.add(s[j]);
    ans = Math.max(ans, j - i + 1);
  }
  return ans;
}

use std::collections::HashSet;

impl Solution {
  pub fn length_of_longest_substring(s: String) -> i32 {
    let s = s.as_bytes();
    let mut ss = HashSet::new();
    let mut i = 0;
    s
      .iter()
      .map(|c| {
        while ss.contains(&c) {
          ss.remove(&s[i]);
          i += 1;
        }
        ss.insert(c);
        ss.len()
      })
      .max()
      .unwrap_or(0) as i32
  }
}

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

public class Solution {
  public int LengthOfLongestSubstring(string s) {
    int ans = 0;
    var ss = new HashSet<char>();
    for (int i = 0, j = 0; j < s.Length; ++j) {
      while (ss.Contains(s[j])) {
        ss.Remove(s[i++]);
      }
      ss.Add(s[j]);
      ans = Math.Max(ans, j - i + 1);
    }
    return ans;
  }
}

class Solution {
  /**
   * @param String $s
   * @return Integer
   */
  function lengthOfLongestSubstring($s) {
    $ans = 0;
    $ss = [];
    for ($i = 0, $j = 0; $j < strlen($s); ++$j) {
      while (in_array($s[$j], $ss)) {
        unset($ss[array_search($s[$i++], $ss)]);
      }
      $ss[] = $s[$j];
      $ans = max($ans, $j - $i + 1);
    }
    return $ans;
  }
}

class Solution {
  func lengthOfLongestSubstring(_ s: String) -> Int {
    var map = [Character: Int]()
    var currentStartingIndex = 0
    var i = 0
    var maxLength = 0
    for char in s {
      if map[char] != nil {
        if map[char]! >= currentStartingIndex {
          maxLength = max(maxLength, i - currentStartingIndex)
          currentStartingIndex = map[char]! + 1
        }
      }
      map[char] = i
      i += 1
    }
    return max(maxLength, i - currentStartingIndex)
  }
}

proc lengthOfLongestSubstring(s: string): int =
  var
  i = 0
  j = 0
  res = 0
  literals: set[char] = {}

  while i < s.len:
  while s[i] in literals:
    if s[j] in literals:
    excl(literals, s[j])
    j += 1
  literals.incl(s[i]) # Uniform Function Call Syntax f(x) = x.f
  res = max(res, i - j + 1)
  i += 1

  result = res # result has the default return value