LeetCode03无重复字符的最长子串

发表于 | 更新于 | 分类于 |

题目描述：

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

示例 1:

1
2
3
输入: "abcabcbb"
输出: 3 
解释: 无重复字符的最长子串是 "abc"，其长度为 3。

示例 2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b"，其长度为 1。

示例 3:

1
2
3
4
输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke"，其长度为 3。
     请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。

思路：

  1. 将length设为1或者0（判断为空字符串，直接return）
  2. 从字符串起始位置开始遍历，在遇到下一个相同的字符之前，都将所遍历经过的字符放到
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    3. 当遇到下一个与之相同的字符时，比较当前```set```长度与整体length，如果大于，则替换length数值。跳转到步骤5
    4. 当没有遇到下一个相同的字符时，说明遍历完了字符串，比较```set```与length长度且赋值，直接返回length，程序结束。
    5. 将起始位置后移一位，继续遍历。此处可以加一个终止条件，就是当得到的length已经比剩下字符串的长度还长之后，就无需再继续遍历了。



    #### 代码实现：

    python 可调试代码地址：https://github.com/zhangdianlei/LeetCode_python/blob/master/src/c03.py

    ```python
    class Solution:
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            if len(str(s)) == 0:
                return 0
            else:
                s = str(s)
                total_length = len(s)
                length = 1
                start = 0

                while start < total_length:
                    tempSet = set()
                    tempSet.add(s[start])

                    for end in range(start+1, total_length):

                        if s[end] not in tempSet:
                            tempSet.add(s[end])
                        else:
                            if len(tempSet) > length:
                                length = len(tempSet)
                            break

                        if end == total_length-1:
                            if len(tempSet) > length:
                                length = len(tempSet)
                            return length
                    start = start + 1

            return length