leecode/problems/3.longestSubstringWithoutRepeatingCharacters.md
2020-05-22 18:17:19 +08:00

2.7 KiB
Raw Permalink Blame History

题目地址

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

题目描述

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

思路

用一个 hashmap 来建立字符和其出现位置之间的映射。

维护一个滑动窗口,窗口内的都是没有重复的字符,去尽可能的扩大窗口的大小,窗口不停的向右滑动。

1如果当前遍历到的字符从未出现过那么直接扩大右边界

2如果当前遍历到的字符出现过则缩小窗口左边索引向右移动然后继续观察当前遍历到的字符

3重复12直到左边索引无法再移动

4维护一个结果 res每次用出现过的窗口大小来更新结果 res最后返回 res 获取结果。

3.longestSubstringWithoutRepeatingCharacters

(图片来自: https://github.com/MisterBooo/LeetCodeAnimation)

关键点

  1. 用一个 mapper 记录出现过并且没有被删除的字符
  2. 用一个滑动窗口记录当前 index 开始的最大的不重复的字符序列
  3. 用 res 去记录目前位置最大的长度,每次滑动窗口更新就去决定是否需要更新 res

代码

代码支持JavaScriptPython3

JavaScript Code:

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  const mapper = {}; // 记录已经出现过的charactor
  let res = 0;
  let slidingWindow = [];

  for (let c of s) {
    if (mapper[c]) {
      // 已经出现过了
      // 则删除
      const delIndex = slidingWindow.findIndex(_c => _c === c);

      for (let i = 0; i < delIndex; i++) {
        mapper[slidingWindow[i]] = false;
      }

      slidingWindow = slidingWindow.slice(delIndex + 1).concat(c);
    } else {
      // 新字符
      if (slidingWindow.push(c) > res) {
        res = slidingWindow.length;
      }
    }
    mapper[c] = true;
  }
  return res;
};

Python3 Code:

from collections import defaultdict


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l = 0
        ans = 0
        counter = defaultdict(lambda: 0)

        for r in range(len(s)):
            while counter.get(s[r], 0) != 0:
                counter[s[l]] = counter.get(s[l], 0) - 1
                l += 1
            counter[s[r]] += 1
            ans = max(ans, r - l + 1)

        return ans