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

• LeetCode 3题

题目描述

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

解题思路

这个题可以用动态规划的思路来解。

• 字符串的长度为N,
• 字符串用S(N)表示
• S(N)中__不含重复字符的最长子串__用NoRepeatSub(N)表示
• NoRepeatSub(N)的长度用L(N)表示

令 S(N) = S(N-1) + char

• char不在S(N-1)中，L(N) = L(N-1) + 1
• char在S(N-1)中:
  • char在NoRepeatSub(N)中, L(N) = L()

代码

https://github.com/bwangelme/LeetCode-Go/tree/master/l3