LeetCode: 3. Longest Substring Without Repeating Characters

引言

题目链接:https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

题目大意

输入一个字符串,输出没有重复字符的最长子串的长度。

例:

  • Example1

Input: "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

  • Example2

Input: "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

题解

一句话题解:利用map或者hash表映射字符和字符上一次出现的位置,当遇到重复字符时(当前符合条件子串结束),查找下一个不包含重复字符的子串起点,同时把当前子串的长度和已有最大值比对记录

  • 详解

映射关系中,保存当前字符在字符串已查询部分中最后出现的下标位置(默认 -1,没有出现过)

  1. 默认第一个子串起点下标为0
  2. 最大值为当前下标和起点下标的差值与存储的最大值的较大者
  3. 当查询到当前字符已经出现过,分两种情况讨论

a). 当前子串的起点下标 > 当前查询字符上一次出现下标位置(证明当前查询字符在当前子串未出现过,如 tmmzuxt,查询最后一个 t当前子串起点为第二个 m

b). 当前子串的起点下标 <= 当前查询字符上一次出现下标位置(证明当前查询字符在当前子串已经出现过一次,当前字符串终结,如 wkew,查询最后一个 w当前子串起点为第一个 w

综上所述,情况一当前子串起点位置大于查询字符上一次出现位置,字符在子串第一次出现,保持起点不变即可,情况二当前子串起点位置小于查询字符第一次出现位置,字符在子串第二次出现,当前子串终结,下一个子串起点重置为当前查询字符出现的下一个下标

lastDiffIndex = lastDiffIndex > index + 1 ? lastDiffIndex : index + 1;

复杂度 O(n)

AC代码

c++版本

go版本


繁夜