每天一道算法：最长无重复子串

3、最长无重复子串

题目

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

给定一个字符串，找到最长的不包含重复字符的子字符串的长度。

示例:

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.

思路

1、暴力求解

双重循环，遍历所有的子串，判断其是否不包含重复字符，并找到最长的子串。双重循环的复杂度为n^2，判断是否包含重复字符的复杂度为n，因此算法整体的复杂度为O(n^3)。

2、动态规划

维护一个词典，里面存放着已经扫描过的字符和位置。每扫描到一个新的元素，判断这个元素是否在词典中，如果在，说明这个元素开始重复了，那这两个位置之间的子串为无重复子串，需要加入到候选列表中。同时，当前子串的起始位置变为第一次出现这个元素的位置的后面一个，这样可以保证尽可能找到不重复且最长的子串。只需要扫描一次，因此算法复杂度为 O(n).

代码

python实现