LeetCode（3）：无重复字符的最大子串

# -*- coding: utf-8 -*-

"""

Created on Sun Mar 10 20:14:53 2019

@author: Administrator

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

Example 1:

Input: "abcabcbb"

Output: 3

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

"""

class Solution:

    def lengthOfLongestSubstring(self, s: str) -> int:

        str_dict = {}   #python中的字典类似于hashmap一样

        start = 0   #定义第一次出现该元素在字典中的位置

        maxLength = 0   #子串的最大的长度

        one_max = 0     #一次循环中子串最长的长度

        for i in range(len(s)):

            #只有当前的字符在字典中并且其位置在最大长子串的起始位置开始

            if s[i] in str_dict and str_dict[s[i]] >= start:

                start = str_dict[s[i]] + 1  #起始位置从当前出现的下一个位置

            one_max = i - start +1  #本次最大的长度为从start到i之间的子串

            str_dict[s[i]] = i      #将其存入字典中

            maxLength = max(one_max,maxLength)  #求最大长度

        '''

        此处应该加上返回最长的子串

        '''

        return maxLength

if __name__ == '__main__':

    s1 = 'abcabcbb'

    s2 = 'abcdcdabcdadcadcdadb'

    solution = Solution()

    answer1 = solution.lengthOfLongestSubstring(s1)

    answer2 = solution.lengthOfLongestSubstring(s2)

    print('MaxLength of abcabcbb:',answer1)

    print('MaxLength of abcdcdabcdadcadcdadb:',answer2)
秒客网

LeetCode（3）：无重复字符的最大子串

相关文章
