Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters leetcode

Medium

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

Example 1:

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

Example 2:

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

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start = -1
        max = 0
        # dictionary d
        d = {} 
        for i in range(len(s)):
            if s[i] in d and d[s[i]] > start:
                start = d[s[i]]
                d[s[i]] = i
            else:
                d[s[i]] = i
                if i - start > max:
                    max = i - start
        return max
        

Sample 3 Explaination

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
Start state: d = {} start = -1(because if  string s is empty ,return 1,if start = 0,then i - start = 0,so initialize start = -1) ,max = 0(longest substring without repeating characters)

 

i d start max
i = 0 {'p':0} -1 1
i = 1 {'p':0,'w':1} -1 2
i = 2 {'p':0,'w':2} 1 2
i = 3 {'p':0,'w':2,'k':3} 1 2
i = 4 {'p':0,'w':2,'k':3,'e':4} 2 1
i = 5 {'p':0,'w':5,'k':3,'e':4} 2 3
上一篇:java – 在四边形OpenGL上重复纹理


下一篇:c# – 列出不应重复填充数据的列表